Monk and Champions League

Monk's favorite game is football, and his favorite club is Manchester United. Manchester United has qualified for the Champions League Final, which is to be held at the Wembley Stadium in London. So, he decided to go there and watch his favorite team play. After reaching the stadium, he saw that many people have lined up for the match tickets. He knows that there are M rows in the stadium with different seating capacities. They may or may not be equal. The price of the ticket depends on the row. If the row has K (always greater than 0) vacant seats, then the price of the ticket will be K pounds (units of British currency). Now, every football fan standing in the line will get a ticket one by one.

Given the seating capacities of different rows, find the maximum possible pounds that the club will gain with the help of the ticket sales.

Input Specification

The first line of the input consists of M and N (1 ≤ M, N ≤ 1 000 000). M denotes the number of seating rows in the stadium, and N denotes the number of football fans waiting in the line to get a ticket for the match. The next line consists of M space-separated integers X₁, X₂, X₃, …, X_M, where X_i denotes the number of empty seats initially in the ith row (1 ≤ X_i ≤ 1 000 000, and the sum of X_i for all 1 ≤ i ≤ M will always be greater than N).

Output Specification

Print in a single line the maximum pounds the club will gain.

Sample Input

1. 3 4
2. 1 2 4

download as text file

Output for Sample Input

1. 11

download as text file

Sample Explanation

In the sample test case, the number of rows is 3, and 4 people are waiting in the line to get a ticket. Since the maximum cost of a ticket initially is 4 pounds, the first person in the line will get a ticket for the 3rd row. The next person standing in the line will again get a ticket for the 3rd row as it has the maximum number of seats, which will cost him 3 pounds. The next person will have 2 choices, he can either choose the 2nd row or the 3rd row, both of which will cost him 2 pounds. Similarly, the last person will get the row with 2 seats remaining, which will cost him 2 pounds. The total cost is 4 + 3 + 2 + 2 = 11 pounds.