← 返回题目列表

AtCoder · awc0018_e

E. 巅峰收藏

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

分数: 433 分

问题陈述

高桥正试图参观 N 山脉沿着横贯路线排成一排。峰顶已编号 1, 2, \ldots, N 从路线的入口侧开始,高桥从入口处出发,从编号较低的山峰单向编号较高的山峰。他无法回到已经走过的巅峰。

每次登顶 i 的“入场费”为 C_i 日元和“海拔” S_i。高桥沿着路线前进,到达每个山顶时,他可以选择攀登或不攀登而通过。如果他没有攀登而经过,则不收取入场费。如果他登上山顶,他必须支付山顶的入场费。

高桥对登山有特殊的偏好,他希望选择攀登的山峰必须满足以下所有条件:

  • 攀登次数上限: 攀登的山峰数量最多为 K.
  • 严格增加海拔: 当攀登的山峰按编号升序排列时,它们的海拔必须严格递增。也就是说,如果他登上顶峰 i_1 < i_2 < \cdots < i_m 按顺序,然后 S_{i_1} < S_{i_2} < \cdots < S_{i_m} 必须保留。
  • 预算限制: 所登顶峰的总入场费不得超过他的资金 B 日元。也就是说, C_{i_1} + C_{i_2} + \cdots + C_{i_m} \leq B 必须保留。

高桥想要 最大化攀登的山峰数量 m 同时满足上述所有条件。找到最大值 m。请注意,不攀登任何山顶(m = 0) 也是允许的。

约束

  • 1 \leq N \leq 500
  • 1 \leq K \leq 50
  • 1 \leq B \leq 500
  • 1 \leq C_i \leq B (1 \leq i \leq N)
  • 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
  • S_i \neq S_j (i \neq j)
  • 所有输入均为整数。

输入

N K B
C_1 S_1
C_2 S_2
\vdots
C_N S_N
  • 第一行包含登顶次数 N,爬升上限 K,以及可用资金 B,用空格分隔。
  • 如下 N 行, i- 第行 (1 \leq i \leq N) 包含入场费 C_i 和海拔 S_i 峰会 i,用空格分隔。

输出

一行打印最大登顶次数 m 满足所有条件即可攀爬。


示例输入 1

5 3 10
3 100
2 200
5 150
4 300
1 400

示例输出 1

3

示例输入 2

4 3 3
2 100
2 200
2 300
2 400

示例输出 2

1

示例输入 3

10 5 20
3 500
2 100
5 300
1 200
4 800
2 600
3 150
6 900
1 700
5 1000

示例输出 3

5

示例输入 4

20 10 50
5 320
3 150
7 410
2 80
4 500
6 230
1 600
8 90
3 700
5 350
2 850
4 120
6 950
1 40
3 1100
7 560
2 1200
5 780
4 1350
3 999

示例输出 4

10

示例输入 5

1 1 1
1 1000000000

示例输出 5

1