Задача D. Марфа Геннадьевна в кустах ≡

Условие

Марфа Геннадьевна считает, что её соседка по даче, Элеонора Агафьевна, слишком любопытна и постоянно подглядывает за Марфой Геннадьевной из окна. Граница участков Марфы Геннадьевны и Элеоноры Агафьевны представляет собой отрезок длиной L см.

Марфа Геннадьевна решила загородить соседке обзор, засадив границу кустами. У Марфы Геннадьевны имеются семена N видов кустов. Известно, что кусты i-го вида вырастают до ширины в a_i см. При этом для нормального развития кустам i-го вида необходимо, чтобы расстояние между краями соседних кустов, а также от края куста до края границы участков было не менее b_i см.

Марфа Геннадьевна желает выбрать один вид кустов таким образом, чтобы суммарная ширина незакрытых кустами участков границы была наименьшей. Напишите программу, которая поможет ей это сделать.

Рекомендуется рассмотреть следующие частичные решения

• N = 1;
• N = 2;

Формат входного файла

Входной файл содержит целые числа N L, за которыми следует N пар целых чисел a_i b_i — ширина куста и минимальное расстояние для i-го вида.

Формат выходного файла

Выходной файл должен содержать единственное целое число — минимальную суммарную ширину не закрытых кустами участков границы.

Ограничения

1 ≤ N ≤ 10³

2 ≤ L ≤ 10⁴

1 ≤ a_i, b_i ≤ 10⁴.

Примеры тестов

2 5
3 1
2 1

2

2 7
3 2
2 3

4

1 10
5 3

10