防御阵（defense）

题目描述

Y 同学正在主持一项古老遗迹的防御阵维护任务。在该遗迹中，有一条长度为 $M$ 的线性走廊，我们可以将其视作数轴上从 $1$ 到 $M$ 的区域。

走廊上分布着 $N$ 座灵力祭坛，编号从 $1$ 到 $N$。第 $i$ 座祭坛位于坐标 $x_i$ 处，其初始的灵力覆盖半径为 $s_i$。这意味着，该祭坛初始时可以保护闭区间 $[x_i - s_i, x_i + s_i]$ 内的所有整数坐标点。

Y 同学可以通过注入法力值来增强祭坛。每消耗 $1$ 单位法力值，可以将任意一座祭坛的灵力覆盖半径增加 $1$。该操作可以对同一座祭坛重复执行多次。

为了确保遗迹的安全，维护任务的目标是：通过增强祭坛，使得走廊内所有整数位置 $k \in \{1, 2, \dots, M\}$ 都被至少一座祭坛的保护范围所覆盖。

请你帮助 Y 同学计算，完成该任务最少需要消耗的法力值总量。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示祭坛的数量和走廊的长度。

接下来的 $N$ 行，每行包含两个整数 $x_i$ 和 $s_i$，分别表示第 $i$ 座祭坛的坐标位置及其初始覆盖半径。

输出格式

输出一行一个整数，表示使得 $[1, M]$ 内所有整数坐标点均被覆盖所需的最少法力值。

样例

样例输入 #1

3 595
43 2
300 4
554 10

样例输出 #1

281

样例输入 #2

1 1
1 1

样例输出 #2

0

样例输入 #3

2 50
20 0
3 1

样例输出 #3

30

样例输入 #4

5 240
13 0
50 25
60 5
155 70
165 70

样例输出 #4

26

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le N \le 80$，$N \le M \le 10^5$，$1 \le x_i \le M$，$0 \le s_i \le M$，且所有的 $x_i$ 互不相同。

• 特殊性质 A：保证对于所有的 $1 \le i \le N$，都有 $s_i = 0$。
• 特殊性质 B：保证所有的祭坛坐标 $x_i$ 均满足 $1 \le x_i \le \frac{M}{2}$。