G - Contest

問題

ビ太郎くんはプログラミングコンテストに出場しています。
コンテストには$N$問の問題があり、$i$問目($1\leq i\leq N$)の問題の難易度は$D_i$です。
このコンテストは、AtsuoCoderのようにプログラムを提出するのではなく、「全ての問題の全てのテストケースの入力ファイルが与えられ、それを手元で実行した出力をテキストで提出する」という形式で行われています(大昔のJOIとかがこういう形式です)。
ビ太郎くんは早解きの天才ですが、計算量改善は苦手です。そのため、ビ太郎くんは各問題に正解するコードは一瞬で書く事ができますが、そのプログラムは$2$秒で実行が終わるとは限らず、$i$問目のテストケースを実行し終わるまでに$T_i$秒かかってしまいます。ビ太郎くんのPCは強いので、複数の問題の解答プログラムを同時に実行する事もできます。
また、ビ太郎くんの体力を$H$とすると、解く問題の難易度の合計が$H$を超える事はできません。
ビ太郎くんの目標は$M$問解く事です。ビ太郎くんが$M$問解き終わるまでには最低何秒かかるでしょう?$M$問解く事が不可能な場合は-1と出力してください。(テストケースを手元で実行する以外にかかる時間は無視できるとします)

制約

• $1\leq M\leq N\leq2\times10^5$
• $1\leq H\leq10^{18}$
• $1\leq D_i,T_i\leq10^9(1\leq i\leq N)$

• 入力はすべて整数

小課題

1. (50点)$N\leq20$
2. (100点)追加の制約はない

入力

$N~M~H$

$D_1~T_1$

$D_2~T_2$

$\vdots$

$D_N~T_N$

入力例1

3 2 4
1 15
3 10
5 12
Copy

出力例1

15
Copy

まず$1$問目と$2$問目を解き、プログラムの実行を同時に始めると、$10$秒経った時点で$2$問目のプログラムが終了し、その$5$秒後に$1$問目のプログラムが終了するので、$15$秒で$2$問解く事ができます。

入力例2

3 2 4
2 15
3 10
5 12
Copy

出力例2

-1
Copy

ビ太郎くんの体力では、$1$問までしか解く事ができません。