题目描述

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

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

每本书的厚度至关重要。悠月希望打磨之后存在一个固定高度 $h$，使得每个位置的上下两本书厚度之和都等于 $h$。同时，为了让书架平稳，上架相邻两本书的厚度差不能超过 $x$。

更形式化地说，设打磨后第 $i$ 个位置的上架厚度为 $a_i$，下架厚度为 $b_i$，则需要满足：

• $a_i+b_i=h$，对所有 $1\le i\le n$ 成立；
• $|a_i-a_{i+1}|\le x$，对所有 $1\le i<n$ 成立；
• $0\le a_i\le u_i$，$0\le b_i\le d_i$。

悠月可以使用古籍打磨机调整厚度。每次操作可以选择任意一本当前厚度大于 $0$ 的书，将它的厚度减小 $1$。每次操作需要支付 $1$ 枚硬币。

悠月不能增加书籍厚度，不能交换书籍位置，也不能修改除厚度外的其他属性。

请你求出，让所有书籍稳定存放在书架上，最少需要支付多少枚硬币。

输入格式

第一行输入两个整数 $n,x$，分别表示书籍数量和上架相邻书籍允许的最大厚度差。

接下来 $n$ 行，每行两个整数 $u_i,d_i$，分别表示第 $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

样例 3

见选手目录下的 book/book3.in 与 book/book3.ans。

该样例满足子任务 $1$ 的约束条件。

样例 4

见选手目录下的 book/book4.in 与 book/book4.ans。

该样例满足子任务 $2$ 的约束条件。

样例 5

见选手目录下的 book/book5.in 与 book/book5.ans。

该样例满足子任务 $3$ 的约束条件。

样例 6

见选手目录下的 book/book6.in 与 book/book6.ans。

该样例满足子任务 $4$ 的约束条件。

样例 7

见选手目录下的 book/book7.in 与 book/book7.ans。

该样例满足子任务 $5$ 的约束条件，且不与正式测试数据重复。

数据范围

对于所有测试数据，均有：

• $2\le n\le 2\times 10^5$；
• $1\le u_i,d_i\le 10^9$；
• $1\le x\le 10^9$。

本题共 $20$ 个测试点，每个测试点 $5$ 分。