AT_awc0001_d.街道の商人

高桥是一名沿着东西方向延伸的高速公路做生意的商人。沿着这条高速公路，排列着 $N$ 个城镇，从西到东分别编号为 $1, 2, \ldots, N$。在第 $i$ 个城镇做生意可以获得 $A_i$ 的利润，但需要花费 $B_i$ 日元作为住宿费用。

高桥决定从这些城镇中选择一些去做生意。但高桥的马车有如下限制：

• 访问的城镇编号不必连续，但当把访问的城镇编号升序排列后，相邻两个编号之间的差必须最多为 $K$。也就是说，若访问的城镇编号升序排列为 $p_1, p_2, \ldots, p_m$，则对于所有 $1 \leq j \leq m-1$ 都有 $p_{j+1} - p_j \leq K$。这是因为马车一次能行驶的距离有限。

高桥能准备的住宿总费用为 $M$ 日元。在选择访问的城镇，使得访问的城镇的住宿总费用不超过 $M$ 日元的前提下，请求出最大可能的总利润。

注意，如果不访问任何城镇，总利润为 $0$。

• 第一行包含 $N$，表示城镇数，$M$，表示可用的住宿总费用，$K$，表示马车一次能行驶的最大城镇数，三者以空格分隔。
• 从第二行到第 $N+1$ 行，每行包含两个整数，依次为 $i$ 号城镇的利润 $A_i$ 和住宿费用 $B_i$，两者以空格分隔。

输出一行，表示在满足条件的情况下，选择城镇所能获得的最大总利润。

数据范围

• $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$
• 所有输入均为整数。

由 ChatGPT 5 翻译