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

Автор:Т. Пакичев, М. Спорышев, А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 103

2 ≤ L ≤ 104

1 ≤ ai, bi ≤ 104.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2 5
3 1
2 1
2
2
2 7
3 2
2 3
4
3
1 10
5 3
10

0.109s 0.008s 13