← 返回题目列表

AtCoder · past23_l

L. 回转寿司

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

问题陈述

高桥和青木来到一家传送带寿司店。最初,每个人的幸福都是 0.

N 寿司菜肴将按顺序接近他们。每道菜总是由高桥或青木拿。
如果 Takahahsi 采取 i第道菜,高桥的幸福感增加了 A_i;如果青木接受的话,青木的幸福感会增加 B_i。在这里,对方的幸福并没有改变。

他们将分发 N 菜肴按顺序排列,使他们的幸福感的绝对差异不超过 M 随时。找到高桥最大可能的最终幸福。

如果他们无法分发 N 菜肴按顺序排列,使他们的幸福感的绝对差异不超过 M 随时报告这一事实。

约束

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 100
  • 1 \leq A_i,B_i \leq 100
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
A_1 B_1
A_2 B_2
\vdots
A_N B_N

输出

在分发高桥时打印出高桥最终的最大幸福 N 菜肴按顺序排列,使他们的幸福感的绝对差异不超过 M 随时。

打印 -1 相反,如果他们无法分发 N 菜肴按顺序排列,使他们的幸福感的绝对差异不超过 M 随时。


示例输入 1

5 7
3 1
4 1
5 9
2 6
5 3

示例输出 1

14

他们可以按如下方式分发菜肴:

  • 高桥拿下 1-st 菜。高桥的幸福就是现在 3,青木的是 0.
  • 高桥拿下 2-第三道菜。高桥的幸福就是现在 7,青木的是 0.
  • 青木拿下 3-rd 菜。高桥的幸福就是现在 7,青木的是 9.
  • 高桥拿下 4第道菜。高桥的幸福就是现在 9,青木的是 9.
  • 高桥拿下 5第道菜。高桥的幸福就是现在 14,青木的是 9.

这会产生最大值,因为无法获得高桥最后的幸福 15 或更大,同时保持他们的幸福感的绝对差异不大于 7.


示例输入 2

5 3
3 1
4 1
5 9
2 6
5 3

示例输出 2

10

他们可以按如下方式分发菜肴:

  • 青木拿下 1-st 菜。高桥的幸福就是现在 0,青木的是 1.
  • 青木拿下 2-第三道菜。高桥的幸福就是现在 0,青木的是 2.
  • 高桥拿下 3-rd 菜。高桥的幸福就是现在 5,青木的是 2.
  • 青木拿下 4第道菜。高桥的幸福就是现在 5,青木的是 8.
  • 高桥拿下 5第道菜。高桥的幸福就是现在 10,青木的是 8.

示例输入 3

5 2
3 1
4 1
5 9
2 6
5 3

示例输出 3

-1

任何分配都会使幸福感的绝对差值大于 2 在某个时刻。


示例输入 4

20 70
22 75
26 45
72 81
47 29
97 2
75 25
82 84
17 56
32 2
28 37
57 39
18 11
79 6
40 68
68 16
40 63
93 49
91 10
55 68
31 80

示例输出 4

496