Автор: | Т. Пакичев, М. Спорышев, А. Кленин | Ограничение времени: | 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 |
|
|
3 |
|
|