Uolevi always goes to dinner at the Market. There are $n$ kinds of food sold. These foods are numbered from $1$ to $n$. The price of one piece of $i$-th food is $p_i$.

Every night, Uolevi will choose a non-empty set of foods and eat one piece of each food in this set. Uolevi likes new things. So he won't choose the same set in two different nights. Besides this, because Uolevi is poor, each night he will choose the cheapest food set that he didn't choose before.

Now, you are given a positive integer $k$. Can you tell Uolevi which set of foods he will choose on $k$-th day? You only have to tell him how much he will spend on this day.

Input

The input consists of two lines. The first line contains integers $n$ and $k$. The second line consists of $n$ integers $p_1, p_2, \ldots p_n$.

Output

Output one number, how much Uolevi will spend on food on $k$-th day.

Constraints

• $2 \le n \le 2 \cdot 10^5$
• $1 \le k \le \min(10^6, 2^n - 1)$
• $1 \le p_i \le 10^8$

Examples

Input:

5 30
4 2 1 16 8

Output:

30

Input:

4 5
1 1 2 2

Output:

2