Эта задача предлагается в двух вариантах, которые отличаются только ограничениями. Если вы можете решить эту задачу в больших ограничениях, то вы можете сразу написать одно решение на оба варианта. Если же решение в больших ограничениях вызывает затруднение, вы можете решить только упрощённый вариант.
Проснувшись с утра, Аполлинария решила испечь печенек. Для того чтобы испечь одну печеньку, нужно n ингредиентов, причем про каждый ингредиент известно число ai — сколько грамм этого ингредиента необходимо для того, чтобы испечь одну печеньку. Для приготовления одной печеньки необходимо использовать все n ингредиентов в нужных пропорциях.
У Аполлинарии есть bi грамм i-го ингридиента. Кроме того, у неё есть k грамм волшебного порошка. Каждый грамм волшебного порошка можно превратить ровно в 1 грамм любого из n ингредиентов и использовать для приготовления печенек.
Перед вами стоит задача — определить максимальное количество печенек, которое сможет испечь Аполлинария при помощи имеющихся у неё ингредиентов и волшебного порошка.
Выходные данные
Выведите целое число — максимальное количество печенек, которые сможет испечь Аполлинария при помощи имеющихся у неё ингредиентов и волшебного порошка.
Примечание
В первом тестовом примере Аполлинарии выгодно превратить 1 имеющийся у неё грамм волшебного порошка в ингредиент номер 2, тогда она сможет испечь 4 печеньки.
Во втором тестовом примере Аполлинарии выгодно превратить 1 грамм волшебного порошка в ингредиент номер 1 и 1 грамм волшебного порошка в ингредиент номер 3. Тогда она сможет испечь 3 печеньки. Оставшийся 1 грамм волшебного порошка можно оставить, так как с помощью него ответ увеличить невозможно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 1
2 1 4
11 3 16
|
4
|
|
2
|
4 3
4 3 5 6
11 12 14 20
|
3
|