配点: 100 点
太郎君决定去参加JOI神社举办的夏日祭。
沿着去JOI神社的路,N 夜摊营业了。每家夜店里,1 从 N 之前的数字按顺序排列,玩的乐趣和玩的时间由整数决定。夜店 玩 i 的乐趣 A_i ,夜店 玩 i 需要多长时间? B_i 。
还有烟火大会作为夏季祭典活动,时间 最大的烟花在 S 燃放。太郎君想看最大的烟花。
太郎君来到夏日祭,享受夜市和烟火。 夏季祭结束时间 0 我决定制定计划直到 T 。
夜店里的太郎君 选择 k 個 (1 \leqq k \leqq N中的夜店,并使用整数决定参观每家夜店的时间。同晚酒吧 2 您无法选择学位。所选夜总会号码按降序排列 y_1,y_2,\ldots,y_k 夜店 y_i 参观时间 x_{y_i} 然后,太郎君在夜间酒吧。 时间在 y_i 当时 x_{yi} 到时间 播放直至 x_{y_i} + B_{y_i} 。
太郎君在夜店按照数字顺序演奏,同时 2 你不能在夜总会玩。另外,夜店之间往返所需的时间可以忽略不计。 如果超过
時刻 T ,夏季祭典就会结束,所以你将无法在夜摊闲逛。另外,在夜店闲逛时也不能观看烟花。然而,时间 S 如果是太郎在某个夜店开始玩或结束玩的时间,则假设太郎可以看到烟花。
换句话说,计划必须满足以下条件。
- y_1 < y_2 < \ldots < y_k
- x_{y_1},x_{y_2},\ldots , x_{y_k} 是一个整数。
- 0\leqq x_{y_1} < x_{y_1} + B_{y_1} \leqq x_{y_2} < x_{y_2} + B_{y_2} \leqq \ldots \leqq x_{y_k} < x_{y_k} + B_{y_k} \leqq T
- x_{y_i} < S < x_{y_i}+B_{y_i} 喜欢 i 不存在。
精选夜店的乐趣 A_{y_1},A_{y_2},\ldots,A_{y_k} 的总和 M 。太郎君是 我想计划使 M 尽可能大。
課題
N 夜店信息及营业时间 当给出 S, T 时, 编写一个程序来查找M 的最大值。
制限
| 1 \leqq N \leqq 3000 | 夜摊数量 |
| 1 \leqq T \leqq 3000 | 夏日祭结束时间 |
| 0 \leqq S \leqq T | 最大烟花燃放时间 玩 |
| 0 \leqq A_i \leqq 100000 \,(= 10^5) | 夜店 i 的乐趣 玩 |
| 0 \leqq B_i \leqq 3000 | 夜店 i 需要多长时间 |
入力
从标准输入读取以下输入。
输入 1 行是一个整数 给出了 N, T, S 以空格为分隔符写入,夜档数为 N 夏日祭结束时间是 T,最大的烟花燃放时间是 S 。
继续 N 行包含有关夜店的信息。输入的 i + 1 (1\leqq i \leqq N) 行是一个整数 给出了 A_i, B_i 以空格作为分隔符写入,夜店 玩 i 的乐趣 玩多久 A_i ,夜店 玩 i 一起玩所需要的时间 B_i 。
此外,对于所有输入,1 您保证能够安排多个预约。
出力
在标准输出上, 表示M 最大值的整数 输出为 1 行。
採点基準
评分数据中,
积分分配 10 对于%,N \leqq 20 很满意。
积分分配 20 对于%,S = 0 很满意。
积分分配 30 对于 %,这些 2 至少满足以下条件之一。还有,这些 2 没有满足这两个条件的评分数据。
入力例 1
5 20 14 8 9 2 4 7 13 6 3 5 8
出力例 1
16
在此示例中,
夜店 1 到时间 访问过 0 ,
夜店 2 到时间 访问过 9 ,
夜店 4 到时间 访问过 14 ,M 可以设为最大。
此时,M = 8 + 2 + 6 = 16 。