Sum Max Plus Min After Decrement Operations

Perform exactly requests operations: first add the sum of the current maximum and the current minimum to the answer, then decrease one of the current maximums by 1. Find the exact final integer total. Both the original array and the values after operations may be negative; when several maximums tie, choosing any of them does not change the resulting multiset.

输入格式

The first line contains n requests and the second line contains n integers. The source only gives requests≥0, an integer array, and the use of sufficiently wide integers; on this site 1≤n≤200000, initial values are in −10^9..10^9, and 0≤requests≤10^12. The answer is not taken modulo anything and may exceed the signed 64-bit range.

输出格式

Output a single integer, the answer.

样例 1

输入：

2 2
1 2

输出：

5

样例 2

输入：

2 5
-1 -1

输出：

-20

样例 3

输入：

3 1
3 3 3

输出：

6

样例说明

The outputs of the three public examples are 5; -20; and 6, checked by independent enumeration or direct simulation.