CF1253E.Antenna Coverage

The mayor of the Central Town wants to modernize Central Street, represented in this problem by the $(Ox)$ axis.

On this street, there are $n$ antennas, numbered from $1$ to $n$. The $i$-th antenna lies on the position $x_i$ and has an initial scope of $s_i$: it covers all integer positions inside the interval $[x_i - s_i; x_i + s_i]$.

It is possible to increment the scope of any antenna by $1$, this operation costs $1$ coin. We can do this operation as much as we want (multiple times on the same antenna if we want).

To modernize the street, we need to make all integer positions from $1$ to $m$ inclusive covered by at least one antenna. Note that it is authorized to cover positions outside $[1; m]$, even if it's not required.

What is the minimum amount of coins needed to achieve this modernization?

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

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

我们可以将任意一根天线的覆盖范围增加 $1$，每次该操作花费 $1$ 枚金币。该操作可执行任意多次（包括对同一根天线重复执行）。

为实现街道现代化，我们需要确保从 $1$ 到 $m$（含端点）的所有整数位置均被至少一根天线覆盖。注意：允许覆盖 $[1,\; m]$ 区间外的位置，即使这并非必需。

实现这一现代化目标所需的最少金币数量是多少？

The first line contains two integers $n$ and $m$ ($1 \le n \le 80$ and $n \le m \le 100\ 000$).

The $i$-th of the next $n$ lines contains two integers $x_i$ and $s_i$ ($1 \le x_i \le m$ and $0 \le s_i \le m$).

On each position, there is at most one antenna (values $x_i$ are pairwise distinct).

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

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

每个位置上至多有一个天线（即所有 $x_i$ 的值两两不同）。

You have to output a single integer: the minimum amount of coins required to make all integer positions from $1$ to $m$ inclusive covered by at least one antenna.

你需要输出一个整数：覆盖从 $1$ 到 $m$（含）的所有整数位置（即每个位置至少被一个天线覆盖）所需的最少天线数量。

In the first example, here is a possible strategy:

• Increase the scope of the first antenna by $40$, so that it becomes $2 + 40 = 42$. This antenna will cover interval $[43 - 42; 43 + 42]$ which is $[1; 85]$
• Increase the scope of the second antenna by $210$, so that it becomes $4 + 210 = 214$. This antenna will cover interval $[300 - 214; 300 + 214]$, which is $[86; 514]$
• Increase the scope of the third antenna by $31$, so that it becomes $10 + 31 = 41$. This antenna will cover interval $[554 - 41; 554 + 41]$, which is $[513; 595]$

Total cost is $40 + 210 + 31 = 281$. We can prove that it's the minimum cost required to make all positions from $1$ to $595$ covered by at least one antenna.

Note that positions $513$ and $514$ are in this solution covered by two different antennas, but it's not important.

—

In the second example, the first antenna already covers an interval $[0; 2]$ so we have nothing to do.

Note that the only position that we needed to cover was position $1$; positions $0$ and $2$ are covered, but it's not important.

在第一个例子中，以下是一种可能的策略：

• 将第一根天线的覆盖范围增加 $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$ 虽然也被覆盖了，但这并不重要。