Antenna Coverage
Contest: Codeforces Round 600 (Div. 2)
Difficulty rating: 2200
Tags: data structures, dp, greedy, sortings

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?

Input format:
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).

Output format:
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.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
3 595
43 2
300 4
554 10

Example output:
281

Example input:
1 1
1 1

Example output:
0

Editorial:
We can add an antenna $$$(x=0, s=0)$$$. It will not modifiy the answer, because it would be non-optimal to increase the scope of this antenna.
Let $$$dp_x$$$ be the minimum cost to cover all positions from $$$x$$$ to $$$m$$$ inclusive, knowing that position $$$x$$$ is covered. We compute $$$dp$$$ in decreasing order of $$$x$$$.
Base case is $$$dp_m := 0$$$.
The default transition is $$$dp_x := (m - x)$$$.
If position $$$x+1$$$ is initially covered, $$$dp_x := dp_{x+1}$$$
Otherwise, let's consider all antennas and their initial intervals $$$[l_i; r_i]$$$. If $$$x < l_i$$$, let $$$u = (l_i - x - 1)$$$, then a possible transition is $$$dp_x := u + dp_{min(m, r_i + u)}$$$.
We take the minimum of all these transitions. Note that we always extend intervals as less as possible, but it's optimal because :
• If after using this interval $$$i$$$, we use another interval $$$j$$$ (at the right of $$$i$$$), the time spent to extend $$$i$$$ could have been used to extend $$$j$$$ instead, which will be more optimal.
• If $$$i$$$ was the last interval used, we don't care because the default transition will take care of this case.
The final answer will be $$$dp_0$$$.
There are $$$O(m)$$$ states and $$$O(n)$$$ transitions, hence final complexity is $$$O(nm)$$$ with very low constant. $$$O(n^2 \cdot m)$$$ can also get AC because of very low constant.
Implementation