Вы можете зарегистрироваться и решать эту задачу здесь.
| Ограничение времени: | 2 с |
| Ограничение реального времени: | 5 с |
| Ограничение памяти: | 256M |
Столовая
В столовой заведения «Покосившийся Скворечник» имеется ровно k тарелок, а в самом заведении – n палат. По старой традиции, чтобы постояльцы не пугались новых знакомых и не обменивались симптомами, их приводят в столовую так, чтобы одновременно там находились только обитатели одной палаты. При этом, порядок посещения столовой палатами строго зафиксирован – от меньшего номера к большему.
Замечено, что некоторые постояльцы всегда моют за собой посуду, другие же – напротив, никогда не моют. Наутро, перед обходом главврача, вся посуда должна быть вымыта нянечками, поэтому завхоз хочет составить такой план выдачи тарелок, чтобы к концу смены нянечкам пришлось мыть их как можно меньше. Конечно же, в этих целях можно выдавать грязные тарелки, оставшиеся от предыдущих палат, постояльцам текущей. Ваша задача – посчитать, какое количество тарелок останется чистым.
Первая строка ввода содержит два целых числа n и k (1 ≤ n ≤ 105, 1 ≤ k ≤ 105) – количество палат и тарелок, соответственно. Следующие n строк содержат по 2 целых числа ai и bi (0 ≤ ai + bi ≤ k) – количество постояльцев в очередной палате, моющих и не моющих за собой посуду, соответственно.
Выведите одно число – количество тарелок, оставшихся чистыми к концу смены, при оптимальной раздаче посуды.
Примеры
| Входные данные | Результат работы |
|
2 4 1 2 1 1 |
3 |
Видеоразбор решения здесь.