You have a fair $n$-sided die with positive integer face values $a_1,a_2,\ldots,a_n$. You want to design another fair $m$-sided die with positive integer face values $b_1,b_2,\ldots,b_m$. Every face of a die is equally likely to be rolled. Face values may repeat on either die.

Roll each die once, independently. The new die wins if and only if its value is strictly greater than the original die’s value; a tie is not a win.

Find the minimum possible sum $b_1+b_2+\cdots+b_m$ of the new die’s face values such that it wins with probability strictly greater than $50\%$.

Input

The first line contains two integers $n,m$ ($2 \le n \le 50$, $1 \le m \le 10^9$), the numbers of faces of the original die and the new die, respectively.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^9$), the face values of the original die.

Output

Print one integer: the minimum possible sum of the new die’s face values such that its probability of winning is strictly greater than $50\%$.

Examples

Input 1

6 6
1 2 3 4 5 6

Output 1

25

Input 2

3 2
1 1 2

Output 2

4

Input 3

4 4
3 7 10 11

Output 3

29

Note

In the first example, an optimal new die has face values $1,1,2,7,7,7$, whose sum is $25$. It wins $0+0+1+6+6+6=19$ of the $36$ equally likely pairs of faces.

In the second example, an optimal new die has face values $2,2$. Each face beats the two faces labeled $1$ on the original die, so the new die wins $4$ of the $6$ equally likely pairs. Its face values sum to $4$.

In the third example, an optimal new die has face values $1,4,12,12$. It wins $0+1+4+4=9$ of the $16$ equally likely pairs, and its face values sum to $29$.