问题陈述
高桥和青木来到一家传送带寿司店。最初,每个人的幸福都是 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