E. Феникс и ягода
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Феникс собирает ягоды у себя на заднем дворе. Там растет $$$n$$$ кустов, и на каждом кусте созрело $$$a_i$$$ красных ягод и $$$b_i$$$ синих ягод.

Каждая корзина вмещает $$$k$$$ ягод. Но Феникс решил, что в каждой корзине могут лежать ягоды с одного куста, или же ягоды одного цвета (красные или синие). Другими словами все ягоды в одной корзине должны быть с одного куста и/или одного цвета.

Например, если у Феникса растет два куста с $$$5$$$ красными и $$$2$$$ синими ягодами на первом кусте и $$$2$$$ красными и $$$1$$$ синей на втором, то он сможет полностью заполнить $$$2$$$ корзины объемом $$$4$$$:

  • в первую корзину он положит $$$3$$$ красные и $$$1$$$ синюю ягоду с первого куста;
  • во вторую корзину — $$$2$$$ оставшиеся красные ягоды с первого куста и $$$2$$$ красные ягоды со второго.

Помогите Фениксу определить максимальное количество корзин, которые он сможет заполнить полностью!

Входные данные

В первой строке заданы два целых числа $$$n$$$ и $$$k$$$ ($$$ 1\le n, k \le 500$$$)  — количество кустов и вместимость корзин, соответственно.

В $$$i$$$-й из следующих $$$n$$$ сток задано два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$0 \le a_i, b_i \le 10^9$$$)  — количество красных и синих ягод на $$$i$$$-м кусте, соответственно.

Выходные данные

Выведите единственное число  — максимальное количество корзин, которые Феникс сможет заполнить полностью.

Примеры
Входные данные
2 4
5 2
2 1
Выходные данные
2
Входные данные
1 5
2 3
Выходные данные
1
Входные данные
2 5
2 1
1 3
Выходные данные
0
Входные данные
1 2
1000000000 1
Выходные данные
500000000
Примечание

Первый пример описан выше.

Во втором примере, Феникс может полностью заполнить одну корзину, используя все ягоды с первого (и единственного) куста.

В третьем примере, Феникс не сможет полностью заполнить ни одной корзины, потому что на каждом кусте меньше $$$5$$$ ягод, всего красных ягод менее $$$5$$$ и всего синих ягод менее $$$5$$$.

В четвертом примере, Феникс может положить все красные ягоды в корзины, оставив синюю ягоду нетронутой.