分数: 500 点
问题陈述
高桥有 2N 牙齿: N 上牙和 N 下牙。
的长度 i左起第 3 颗上牙 (1 \leq i \leq N) 是 U _ i,以及长度 i左起第 下齿 (1 \leq i \leq N) 是 D _ i.
如果满足以下两个条件,则据说他的牙齿“吻合良好”:
- 存在一个整数 H 这样 U _ i + D _ i = H 对于每个整数 i 与 1 \leq i \leq N.
- \lvert U _ i - U _ {i+1} \rvert \leq X 对于每个整数 i 与 1 \leq i < N.
他可以执行以下操作任意次:
- 支付 1 日元使用磨齿机,选择一个长度为正的牙齿,并将其长度减少 1.
不得使用其他方法来改变齿的长度。
求出他需要支付的最少总金额才能使他的牙齿完美贴合。
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq U _ i \leq 10^9 \ (1 \leq i \leq N)
- 1 \leq D _ i \leq 10^9 \ (1 \leq i \leq N)
- 1 \leq X \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N X U _ 1 D _ 1 U _ 2 D _ 2 \vdots U _ N D _ N
输出
打印答案。
示例输入 1
4 3 3 1 4 1 5 9 2 6
示例输出 1
15
最初,高桥的牙齿有以下长度:

例如,您可以通过以下方式使它们很好地结合在一起:

成本 15 日元才能达到这些长度。
不可能让它们与 14 日元或更少,所以打印 15.
示例输入 2
4 1000000000 3 3 3 3 3 3 3 3
示例输出 2
0
牙齿可能已经很好地配合在一起,没有任何改变。
示例输入 3
4 1 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1 1
示例输出 3
5999999994
请注意,答案可能会超出 32- 位整数范围。
示例输入 4
15 128 748 169 586 329 972 529 432 519 408 587 138 249 656 114 632 299 984 755 404 772 155 506 832 854 353 465 387 374 567 385
示例输出 4
9460