Феникс собирает ягоды у себя на заднем дворе. Там растет \(n\) кустов, и на каждом кусте созрело \(a_i\) красных ягод и \(b_i\) синих ягод.
Каждая корзина вмещает \(k\) ягод. Но Феникс решил, что в каждой корзине могут лежать ягоды с одного куста, или же ягоды одного цвета (красные или синие). Другими словами все ягоды в одной корзине должны быть с одного куста и/или одного цвета.
Например, если у Феникса растет два куста с \(5\) красными и \(2\) синими ягодами на первом кусте и \(2\) красными и \(1\) синей на втором, то он сможет полностью заполнить \(2\) корзины объемом \(4\):
- в первую корзину он положит \(3\) красные и \(1\) синюю ягоду с первого куста;
- во вторую корзину — \(2\) оставшиеся красные ягоды с первого куста и \(2\) красные ягоды со второго.
Помогите Фениксу определить максимальное количество корзин, которые он сможет заполнить полностью!
Выходные данные
Выведите единственное число — максимальное количество корзин, которые Феникс сможет заполнить полностью.
Примечание
Первый пример описан выше.
Во втором примере, Феникс может полностью заполнить одну корзину, используя все ягоды с первого (и единственного) куста.
В третьем примере, Феникс не сможет полностью заполнить ни одной корзины, потому что на каждом кусте меньше \(5\) ягод, всего красных ягод менее \(5\) и всего синих ягод менее \(5\).
В четвертом примере, Феникс может положить все красные ягоды в корзины, оставив синюю ягоду нетронутой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 4
5 2
2 1
|
2
|
|
2
|
1 5
2 3
|
1
|
|
3
|
2 5
2 1
1 3
|
0
|
|
4
|
1 2
1000000000 1
|
500000000
|