I - Homework
Editorial
/
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
- 答えが大きくなりうることに注意してください