B. 书架平衡

题目描述

在古籍修复师悠月的工坊中，有两个并排的檀木书架：

• 上架：摆放着 $n$ 本古籍善本。
• 下架：对应摆放着 $n$ 本古籍注释。

每本书的厚度至关重要，它们必须满足“平衡法则”才能稳定存放：

• 高度守恒：存在固定高度 $h$，使上下架第 $i$ 位书籍厚度之和恒为 $h$，即上架书籍厚度 $u_i$ $+$ 下架书籍厚度 $d_i = h$（对所有 $1 \le i \le n$）。
• 平滑过渡：上架相邻书籍厚度差不超过 $x$，即 $|u_i - u_{i+1}| \le x$（对所有 $1 \le i < n$）。

悠月可以使用古籍打磨机调整厚度，每次操作可以选择任意一本厚度 $>0$ 的书，将其厚度减小 1 个单位。每次操作需要支付 1 枚硬币。悠月不能增加书籍厚度，交换书籍位置，修改除厚度外的其他属性。

悠月需要让所有书籍稳定存放在书架上，她最少需要支付多少枚硬币。

输入格式

第一行输入两个整数 $n$，$x$，分别表示书籍数量，相邻书籍满足“平衡法则”的最大高度差。

接下来 $n$ 行，每行两个整数 $u_i$，$d_i$，分别表示上架书籍厚度、下架书籍厚度。

输出格式

输出一个整数，表示答案。

样例输入1

4 3
3 1
4 1
5 9
2 6

样例输出1

15

样例输入2

4 1000000000
3 3
3 3
3 3
3 3

样例输出2

0

数据范围

• 对于 $10\%$ 的数据，$2 \le n \le 10$，$1 \le u_i, d_i \le 10^3$ ($1 \le i \le n$)，$1 \le x \le 10^9$。
• 对于 $50\%$ 的数据，$2 \le n \le 10^3$，$1 \le u_i, d_i \le 10^3$ ($1 \le i \le n$)，$1 \le x \le 10^9$。
• 对于 $100\%$ 的数据，$2 \le n \le 2 \times 10^5$，$1 \le u_i, d_i \le 10^9$ ($1 \le i \le n$)，$1 \le x \le 10^9$。