You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

小美打算购买水果，她的本月采购预算为 $B$ 元，希望挑选 恰好 $k$ 种 水果，既满足总价格不超过预算，又能让所选水果的最小甜度尽可能高。甜度是水果的重要品质指标，数值越大表示水果越甜。我们的目标是在满足预算约束的前提下，找到这样的水果组合，使得其中甜度最低的水果的甜度尽可能大。

题目描述

现在给定 $n$ 种水果的甜度 $a_i$ 和价格 $c_i$，请帮小美选出 恰好 $k$ 种 水果，满足：

1. 总价格不超过预算 $B$
2. 所有选中水果的 最小甜度尽可能大

如果无法满足条件（比如买不够 $k$ 种水果或总价必然超预算）（输出 -1）。

输入格式

第一行：

三个整数 $n$（水果种类数）、$B$（预算，单位：元）、$k$（需挑选的水果种类数，必须恰好选 k 种）。 接下来 $n$ 行：每行两个整数 $a_i$（甜度）和 $c_i$（价格，单位：元）。

输出格式

输出一个整数，表示 最大的最小甜度。如果无法满足要求，输出 -1。

输入输出样例 #1

输入 #1

5 100 3  
50 40  
30 20  
25 10  
55 60  
15 5  

输出 #1

25

说明

小美需要选3种水果，总价不超过100元。
如果选甜度50（40元）、30（20元）、55（60元），总价120元超预算。
最佳方案是选甜度30（20元）、25（10元）、15（5元）？不行，因为最小甜度15太低。
正确选法是选甜度25（10元）、30（20元）、50（40元），总价70元，最小甜度25，且无法找到更大的最小甜度满足条件。

输入输出样例 #2

输入 #2

3 50 2  
20 10  
20 20  
20 30  

输出 #2

20

说明

所有水果甜度都是20，选任意2种总价不超过50元（如10+20=30元），最小甜度自然是20。

数据范围

对于 $40\%$ 的数据， $1 ≤ n ≤ 100$ ，$1 ≤ B ≤ 1000$ ， $1 ≤ a_i ≤ 1000$ ， $1 ≤ c_i ≤ 1000$

对于 $100\%$ 的数据，保证$1 ≤ n ≤ 10^5$ ，$1 ≤ B ≤ 10^9$ ， $1 ≤ k ≤ n$ ， $1 ≤ a_i ≤ 10^9$ ，$1 ≤ c_i ≤ 10^9$

• 时间限制: $1 s$
• 空间限制: $256 MB$