問題文

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

宿題は $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}$
• 与えられる入力は全て整数

入力例 1Copy

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

出力例 1Copy

7

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

入力例 2Copy

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

出力例 2Copy

98

入力例 3Copy

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

出力例 3Copy

5368709120

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