D - コンテストの準備 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

高橋君はプログラミングコンテストを開催するために、N 問の候補問題の中から相異なる K 問を選んで出題することにしました。

候補問題には 1 から N までの番号が付けられており、問題 i の配点は A_i 点、難易度は B_i です。

高橋君は、選んだ K 問の配点の合計を P 点以上にする必要があります。

また、参加者が挑戦しやすいように、選んだ K 問の難易度の最大値をできるだけ小さくしたいと考えています。

配点の合計が P 点以上となるように K 問を選んだときの、選ばれた問題の難易度の最大値として考えられる最小値を求めてください。

ただし、どのように K 問を選んでも配点の合計が P 点以上にならない場合は、代わりに -1 を出力してください。

制約

  • 1 \leq K \leq N \leq 10^5
  • 1 \leq P \leq 10^{14}
  • 1 \leq A_i \leq 10^9
  • 1 \leq B_i \leq 10^9
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N K P
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

配点の合計が P 点以上となるように相異なる K 問を選んだときの、選ばれた問題の難易度の最大値の最小値を 1 行で出力してください。

ただし、どのように選んでも配点の合計が P 点以上にならない場合は、代わりに -1 を出力してください。

入力例 1

4 2 100
60 200
50 300
40 100
70 400

出力例 1

200

入力例 2

3 2 100
30 10
40 20
20 30

出力例 2

-1

入力例 3

8 4 300
80 500
120 700
50 200
90 450
70 300
110 600
60 250
100 400

出力例 3

450

入力例 4

15 6 2500000000
600000000 450000000
300000000 120000000
750000000 890000000
400000000 330000000
550000000 610000000
200000000 150000000
800000000 950000000
350000000 280000000
500000000 500000000
650000000 700000000
450000000 400000000
250000000 220000000
700000000 780000000
150000000 100000000
580000000 640000000

出力例 4

500000000

入力例 5

1 1 500
500 12345

出力例 5

12345

Score : 400 pts

Problem Statement

Takahashi has decided to hold a programming contest by selecting K distinct problems from N candidate problems.

The candidate problems are numbered 1 through N, and problem i has a score of A_i and a difficulty of B_i.

Takahashi needs the total score of the chosen K problems to be at least P.

Additionally, to make the contest more accessible to participants, he wants to minimize the maximum difficulty among the chosen K problems.

Find the minimum possible value of the maximum difficulty among the chosen problems when selecting K problems such that the total score is at least P.

If it is impossible to achieve a total score of at least P no matter how the K problems are chosen, output -1 instead.

Constraints

  • 1 \leq K \leq N \leq 10^5
  • 1 \leq P \leq 10^{14}
  • 1 \leq A_i \leq 10^9
  • 1 \leq B_i \leq 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N K P
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Print the minimum possible value of the maximum difficulty among the chosen problems when selecting K distinct problems such that the total score is at least P in a single line.

If it is impossible to achieve a total score of at least P no matter how the problems are chosen, print -1 instead.

Sample Input 1

4 2 100
60 200
50 300
40 100
70 400

Sample Output 1

200

Sample Input 2

3 2 100
30 10
40 20
20 30

Sample Output 2

-1

Sample Input 3

8 4 300
80 500
120 700
50 200
90 450
70 300
110 600
60 250
100 400

Sample Output 3

450

Sample Input 4

15 6 2500000000
600000000 450000000
300000000 120000000
750000000 890000000
400000000 330000000
550000000 610000000
200000000 150000000
800000000 950000000
350000000 280000000
500000000 500000000
650000000 700000000
450000000 400000000
250000000 220000000
700000000 780000000
150000000 100000000
580000000 640000000

Sample Output 4

500000000

Sample Input 5

1 1 500
500 12345

Sample Output 5

12345