配点 : 575 点
問題文
AtCoder Land 有 N 个游乐设施。
i 第 2 个游乐设施有以下
- 种获取方法。
- A_i 正常购买。
- 分钟后结束。
- B_i 使用快速通行证。 1 分钟后追加项目结束。此时会消耗
张快速通行证。 K 张快速通行证。
假设不会多次乘坐同一个游乐设施, T 分钟后最多可以乘坐多少个游乐设施?
但是,请注意可以忽略乘坐游乐设施之间的换乘时间,并且最后乘坐的游乐设施 T 必须在分钟后结束乘坐。
制約
- 输入中的所有数值均为整数
- 1 \le K \le N \le 2 \times 10^5
- 1 \le T \le 10^{18}
- 1 \le B_i \le A_i \le 10^{12}
入力
输入从标准输入按以下格式给出。
N K T A_1 B_1 A_2 B_2 \vdots A_N B_N
出力
请将答案作为整数输出。
入力例 1
5 2 20 7 4 10 8 3 3 8 7 9 5
出力例 1
4
在该输入中,AtCoder Land 有 5 个游乐设施 2 张快速通行证。
- 首先, 5 使用快速通行证乘坐第个游乐设施。
- 此时, 5 分钟后乘坐结束,快速通行证剩余 1 张。总共经过了 5 分钟。
- 接下来, 3 按通常方式乘坐第个游乐设施。
- 此时, 3 分钟后乘坐结束。总共经过了 8 分钟。
- 接下来, 1 使用快速通行证乘坐第个游乐设施。
- 此时, 4 分钟后乘坐结束,快速通行证剩余 0 张。总共经过了 12 分钟。
- 最后, 4 按通常方式乘坐第个游乐设施。
- 此时, 8 分钟后乘坐结束。总共经过了 20 分钟。
按照上述方式,可以乘坐 4 个游乐设施,并且可以证明这是最大值。
入力例 2
5 5 1 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000
出力例 2
0
T 也有可能在规定时间内一个 atorakushon 都无法完成的情况。
入力例 3
5 5 1000000000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000
出力例 3
5
T 也有可能在规定时间内采购全部 eaterakushon。
入力例 4
15 4 60 9 4 8 8 10 10 7 6 10 3 6 6 8 7 9 5 6 5 4 2 1 1 7 6 8 6 6 4 4 3
出力例 4
12