E. Покрытие антеннами
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Мэр Центрального Города решил модернизировать Центральную Улицу, представленную в этой задаче в виде оси $$$(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 \le n \le 80$$$ и $$$n \le m \le 100\ 000$$$).

В $$$i$$$-й из следующих $$$n$$$ строк записаны два целых числа $$$x_i$$$ и $$$s_i$$$ ($$$1 \le x_i \le m$$$ and $$$0 \le s_i \le m$$$).

На каждой позиции стоит не более одной антенны (все позиции $$$x_i$$$ попарно различны).

Выходные данные

Выведите одно целое число: минимальное количество монет, которое нужно, чтобы все позиции от $$$1$$$ до $$$m$$$ покрывались хотя бы одной антенной.

Примеры
Входные данные
3 595
43 2
300 4
554 10
Выходные данные
281
Входные данные
1 1
1 1
Выходные данные
0
Входные данные
2 50
20 0
3 1
Выходные данные
30
Входные данные
5 240
13 0
50 25
60 5
155 70
165 70
Выходные данные
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$$$ покрыты, но это не важно.