Max Transfer Rate

Choose pipelineCount distinct ordered index pairs (i,j); each pair contributes throughput[i]+throughput[j]. i=j is allowed, and (i,j) and (j,i) are different; different servers with the same capacity also have different identities. Find the maximum total.

输入格式

The first line contains n pipelineCount; the second line contains throughput. The original text had no numeric bounds; this site uses 1≤n≤200000, 1≤throughput[i]≤10^9, 1≤pipelineCount≤n²; use 64 bits for K. This site requires the exact integer to be output; the maximum answer 8×10^19 exceeds the signed 64-bit range, and no modulo is taken.

输出格式

Output a single integer, the answer.

样例 1

输入：

3 4
4 2 5

输出：

36

样例 2

输入：

2 4
2 2

输出：

16

样例 3

输入：

2 3
1 10

输出：

42

样例说明

The answers are 36, 16 and 42. In the third example the top 3 are 20, 11 and 11, and both directions must be counted.