配点: 1000 点
重要提示:这个问题在《竞争性编程的黄金法则》一书中两次讨论,分别在 6.4 和 8.3 节中。请注意,第 6.4 节中的解决方案可能只会给您部分分数(第 8.3 节中的解决方案可能会给您满分)。
問題文
太郎今天开始 D 我决定工作几天。 工作选择是 N 可用,i 第二个工作是 X_i 当天之后,你可以选择,一旦完成, Y_i 您将收到日元。 1 做两份工作 1 太郎一天最多能赚到多少日元?
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq D \leq 2000
- 1 \leq X_i \leq D
- 1 \leq Y_i \leq 10^6
- 所有输入均为整数
(2022/10/05 2:00 追記) D 约束 365 减去 2000 并重新创建测试用例。 如果所有满足
部分点
N \leq 2000 的测试用例都得到正确回答,200 积分。
入力
输入是按以下格式从标准输入给出的。
N D X_1 Y_1 \vdots X_N Y_N
出力
请以整数形式输出答案。
入力例 1
5 4 1 1 2 4 2 3 3 4 4 2
出力例 1
12
1 個目、2 個目、4 個目、3 如果您按照以下顺序工作 1+4+4+3=12 这是您可以获得的最大值。