分数: 400 分
问题陈述
高桥是一位商人,沿着东西延伸的高速公路做生意。有 N 城镇沿着这条高速公路排成一排,编号 1, 2, ..., N 从西到东。在以下地区开展业务 i第镇的利润为 A_i,但成本 B_i 日元作为住宿费。
高桥决定选择其中一些城镇开展业务。但是,高桥的马车有以下限制:
- 访问过的城镇不需要有连续的编号,但是当访问过的城镇编号按升序排列时,任意两个相邻编号之间的差值最多为 K。换句话说,如果按升序访问的城镇编号为 p_1, p_2, \ldots, p_m,那么 p_{j+1} - p_j \leq K 必须适用于所有 1 \leq j \leq m - 1。这是因为马车一次可以行驶的距离是有限制的。
高桥可以准备的住宿费用总计为 M 日元。选择城镇时,使所访问城镇的住宿总费用最多为 M 日元,求最大可能的总利润。
请注意,如果没有访问任何城镇,则总利润为 0.
约束
- 1 \leq N \leq 200
- 1 \leq M \leq 200
- 1 \leq K \leq N
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq M
- 所有输入均为整数
输入
N M K A_1 B_1 A_2 B_2 : A_N B_N
- 第一行包含 N 代表城镇数量, M 代表可用的住宿费用总额,以及 K 代表一次可以到达的最大城镇数量,以空格分隔。
- 从第 2 行到 (N + 1)第行,给出了每个城镇的信息。
- 的 (1 + i)-第行包含利润 A_i 可在 i第城镇及住宿费用 B_i,用空格分隔。
输出
在一行中输出选择满足条件的城镇时可能获得的最大利润总额。
样本输入 1
5 10 2 8 3 5 4 10 5 3 2 7 3
示例输出 1
21
示例输入 2
4 5 1 100 2 200 3 150 2 50 1
示例输出 2
350
示例输入 3
10 50 3 1000000000 10 500000000 8 800000000 12 300000000 5 600000000 15 900000000 20 400000000 7 700000000 11 200000000 6 550000000 9
示例输出 3
3450000000