← 返回题目列表

AtCoder · awc0001_d

D. 高速公路上的商人

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

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