問題文

高橋君は夏休みの宿題を片付けることにしました。

宿題は $1$ から $N$ までの番号がついた $N$ 個の問題からなります。 問題 $i$ は解くのに $2^{A_i}$ 秒かかり、$B_i$ 点だけ得点が得られます。

高橋君は得られた得点の総和が $K$ 以上になるように問題を解く必要があります。これを達成するために必要な時間の最小値を求めてください。

制約

• $1 \\leq N \\leq 10^{5}$
• $0 \\leq A_i \\leq 30$
• $1 \\leq B_i \\leq 10^{9}$
• $1 \\leq K \\leq Σ{B_i}$
• 与えられる入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

$N$ $K$ $A_1$ $B_1$ $:$ $A_{N}$ $B_{N}$

出力

答えを出力せよ。

入力例 1

6 24
1 5
0 4
1 9
2 10
2 11
3 15

出力例 1

7

• 問題 $2,3,5$ を解くと、$7$ 秒間で $24$ 点が得られ、これが最適です。

入力例 2

13 105
0 1
3 8
5 28
0 1
0 2
4 17
5 26
5 33
3 8
4 19
3 7
2 4
4 17

出力例 2

98

入力例 3

5 5000000000
30 1000000000
30 1000000000
30 1000000000
30 1000000000
30 1000000000

出力例 3

5368709120

• 答えが大きくなりうることに注意してください