题目描述

中央镇的市长希望对中央大街进行现代化改造，在本题中，中央大街用 $(Ox)$ 轴表示。

在这条街上有 $n$ 个天线，编号从 $1$ 到 $n$。第 $i$ 个天线位于位置 $x_i$，初始覆盖范围为 $s_i$：它可以覆盖区间 $[x_i - s_i,\, x_i + s_i]$ 内的所有整数位置。

你可以将任意天线的覆盖范围增加 $1$，每次操作花费 $1$ 个金币。你可以对同一个天线进行多次操作。

为了完成街道的现代化，需要使得所有从 $1$ 到 $m$ 的整数位置都被至少一个天线覆盖。注意，允许覆盖 $[1,\, m]$ 以外的位置，即使这些位置不需要被覆盖。

请问，最少需要多少金币，才能完成这项现代化改造？

输入格式

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 80$，$n \leq m \leq 100\,000$）。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $s_i$（$1 \leq x_i \leq m$，$0 \leq s_i \leq m$）。

每个位置最多只有一个天线（即 $x_i$ 两两不同）。

输出格式

输出一个整数，表示使得所有 $1$ 到 $m$ 的位置都被至少一个天线覆盖所需的最小金币数。

输入输出样例 #1

输入 #1

3 595
43 2
300 4
554 10

输出 #1

281

输入输出样例 #2

输入 #2

1 1
1 1

输出 #2

0

输入输出样例 #3

输入 #3

2 50
20 0
3 1

输出 #3

30

输入输出样例 #4

输入 #4

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

输出 #4

26

说明/提示

在第一个样例中，一种可行的策略如下：

• 将第一个天线的覆盖范围增加 $40$，使其变为 $2 + 40 = 42$。此时该天线覆盖区间 $[43 - 42,\, 43 + 42]$，即 $[1,\, 85]$。
• 将第二个天线的覆盖范围增加 $210$，使其变为 $4 + 210 = 214$。此时该天线覆盖区间 $[300 - 214,\, 300 + 214]$，即 $[86,\, 514]$。
• 将第三个天线的覆盖范围增加 $31$，使其变为 $10 + 31 = 41$。此时该天线覆盖区间 $[554 - 41,\, 554 + 41]$，即 $[513,\, 595]$。

总代价为 $40 + 210 + 31 = 281$。可以证明，这是使得所有 $1$ 到 $595$ 的位置都被至少一个天线覆盖所需的最小代价。

注意，在本方案中，位置 $513$ 和 $514$ 被不同的天线重复覆盖，但这并不影响结果。

——

在第二个样例中，第一个天线已经覆盖了区间 $[0,\, 2]$，因此无需进行任何操作。

注意，唯一需要被覆盖的位置是 $1$；位置 $0$ 和 $2$ 也被覆盖了，但这并不重要。