← 返回题目列表

AtCoder · codequeen2024_final_h

H. 再见,AtCoder Land。

中文机器翻译题面 查看原题

配点 : 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