| Автор: | Антон Феськов, Фёдор Царёв | Ограничение времени: | 2 сек | |
| Входной файл: | fitness.in | Ограничение памяти: | 256 Мб | |
| Выходной файл: | fitness.out |
В последнее время фитнесс-клубы стали очень популярны среди жителей столицы Флатландии. В такие клубы люди ходят после работы для того, чтобы поддерживать себя в хорошей физической форме. В фитнесс-клубe "Флат" каждому из посетителей на время посещения выделяется один из k шкафчиков, в который он может убрать свои вещи на время тренировки.
В течение дня в фитнесс-клубе проходит n тренировок, причем каждый из посетителей приходит к началу какой-либо из этих тренировок (в этот момент он получает ключ от шкафчика) и уходит сразу после ее окончания (в этот момент он сдает ключ от шкафчика). При этом можно считать, что все посетители, закончившие тренировку, уходят раньше, чем все посетители, пришедшие на следующую тренировку.
Некоторые из посетителей уходя закрывают шкафчик, а другие — не закрывают. Так как все посетители фитнесс-клуба посещают его уже достаточно давно, то про каждого из них персонал клуба знает, закроет ли он свой шкафчик, когда будет уходить. Таким образом, для каждой тренировки известно два числа: число ai посетителей, которые закроют шкафчик, и число bi посетителей, которые не закроют.
В начале дня все k шкафчиков закрыты. Разумеется, персоналу клуба хочется, чтобы в конце дня также как можно больше шкафчиков были закрыты — тогда надо будет меньше работать при подготовке к очередному дню. Для того, чтобы достичь этой цели, персонал может выдавать ключи от шкафчиков посетителям произвольным образом. Например, имеет смысл выдавать ключ от открытого шкафчика тому, кто его точно закроет.
Необходимо найти максимальное число шкафчиков, которые окажутся закрытыми, в случае оптимальных действий персонала фитнесс-клуба.
Первая строка входного файла содержит два целых числа: n (1 ≤ n ≤ 100) и k (1 ≤ k ≤ 1000). Каждая из последующих n строк содержит по два целых числа ai и bi (0 ≤ ai, bi ≤ k, ai + bi ≤ k).
В выходной файл выведите одно число — ответ на задачу.
Комментарий к примеру. Пронумеруем шкафчики числами от 1 до 4. Посетителям, пришедшим на первую тренировку выдадим ключи так: тому, кто закроет, — от шкафчика 1, тем, кто не закроет, — от 2 и 3. Посетителям, пришедшим на вторую тренировку, выдадим ключи так: тому, кто закроет, — номер 2, тому, кто не закроет, — номер 3. В итоге открытым после окончания дня останется только шкафчик номер 3.| № | Входной файл (fitness.in) |
Выходной файл (fitness.out) |
|---|---|---|
| 1 | |
|