Maximize Rental Revenue (VM Stock)

There are n kinds of virtual machines, with initial stock vmStock[i]. Serve up to m customers in order. Each customer first pays the sum of the current maximum stock and the current minimum non-zero stock, then rents one machine from a type that currently has the maximum stock, decreasing its stock by one. Zero stocks are excluded from the minimum. Based on the consistent behavior of the fixed source's Python, Java, and C++ code, this site specifies: stop immediately once all stock is exhausted and output the revenue accumulated so far; when the maximum is tied, choosing any of them does not affect the result.

输入格式

The first line contains two integers n m, and the second line contains n integers vmStock[i]. Complete original constraints: 1≤n≤10^6, 1≤m≤10^6, 1≤vmStock[i]≤10^6. The size limit for a single test input on this site is 32 MiB.

输出格式

Output the accumulated revenue, using an integer type large enough to hold 2×10^12. Customers who arrive after the stock runs out generate no revenue.

样例 1

输入：

2 3
2 3

输出：

12

样例 2

输入：

1 5
1

输出：

2

样例 3

输入：

1 3
3

输出：

12

样例说明

Example 1 charges 5, 4, 3 in turn, 12 in total; example 2 can only serve the first customer, revenue 2; example 3 charges 6, 4, 2 in turn, 12 in total.