Мэр Центрального Города решил модернизировать Центральную Улицу, представленную в этой задаче в виде оси \((Ox)\).
На этой улице стоит \(n\) антенн, пронумерованных от \(1\) до \(n\). \(i\)-я антенна стоит в точке \(x_i\) и имеет изначальный радиус \(s_i\): Она покрывает все целые точки в интервале \([x_i - s_i; x_i + s_i]\).
Возможно увеличить радиус любой антенны на \(1\), эта операция стоит \(1\) монету. Мы можем выполнять эту операцию сколько угодно раз (несколько раз для одной и той же антенны, если хотим).
Чтобы модернизировать улицу, нам необходимо, чтобы все целые точки от \(1\) до \(m\) включительно были покрыты хотя бы одной антенной. Обратите внимание, что разрешается покрывать точки за пределами интервала \([1; m]\), однако, это не требуется.
Какое минимальное количество монет требуется, чтобы добиться модернизации?
Выходные данные
Выведите одно целое число: минимальное количество монет, которое нужно, чтобы все позиции от \(1\) до \(m\) покрывались хотя бы одной антенной.
Примечание
В первом примере, одна из возможных стратегий это:
- Увеличить радиус первой антенны на \(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\) покрыты, но это не важно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 595
43 2
300 4
554 10
|
281
|
|
2
|
1 1
1 1
|
0
|
|
3
|
2 50
20 0
3 1
|
30
|
|
4
|
5 240
13 0
50 25
60 5
155 70
165 70
|
26
|