問題文

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

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

入力例 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

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