I - Homework

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1000

問題文

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

宿題は 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
  • 答えが大きくなりうることに注意してください