← 返回题目列表

AtCoder · joi2012ho3

C. 夜市

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

配点: 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 。