分数: 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