UOJ Logo Universal Online Judge

UOJ

附件下载 统计

Page of Clubs, where numbers align in groups of three with cunning grace.

给定 3n 个正整数 x1,x2,,x3n,现在你需要将其划分为互不相交的 n 个三元组。

对于每个三元组,假设将元素排好序后为 (a,b,c),即 abc,则其代价为 b(ca)

现在你需要回答以最优的方式划分,代价和最小为多少。

输入格式

第一行输入一个正整数 n

第二行输入 3n 个单调不降的正整数 x1,x2,,x3n

输出格式

一行一个整数表示答案。

样例一

input

2
1 2 3 4 5 6

output

14

explanation

最优的划分为 [(1,2,3),(4,5,6)],代价和为 2×(31)+5×(64)=14

样例二

input

2
1 2 4 8 16 32

output

158

explanation

最优的划分为 [(1,2,32),(4,8,16)],代价和为 2×(321)+8×(164)=158

样例三~六

见附件下载。

限制与约定

对于所有数据,保证 1n3001xi106,且 x 单调不降。

子任务编号 n x3n 分值
1 8 106 20
2 20 3 20
3 50 106 20
4 100 3 20
5 300 106 20

时间限制:1s

空间限制:512MB