Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Задача B. Бразды

Задачу добавил: alef

Успешно сдано решений: 26

Пока царица Марья собирает чемоданы для путешествия, царь Симеон наставляет царевича Елисея - что да как делать нужно. Вроде бы и просто все: с утра доклады Смотрителя Границы о состоянии дел на границе государственной выслушать - случается, олень с золотыми рогами из двунадесятого королевства забегает, так по соглашению, его надобно изловить и вернуть, да Казначея о состоянии казны - сколько убыло, сколько прибыло; днем о делах хозяйственных совещание провести...
Выслушал это все Елисей и загрустил: это же весь день только государственными делами заниматься надо. А столько всего еще хочется - и погулять, и с друзьями пообщаться, и фильм новый посмотреть...
- Ничего, это поначалу много времени занимать будет, - утешил его Симеон. - Научишься, и дело куда как быстрее пойдет! И времени на все хватит, еще и останется.
Каждый день Елисей должен исполнить N государственных дел, на каждое из которых в настоящий момент он затрачивает T1, T2, ..., TN единиц времени соответственно. Он совершенствует свои навыки в исполнении государственных дел. Так, чтобы научиться выполнять дело #j за Tj-1 единицу времени, ему потребуется Kj дней, чтобы выполнять его за Tj-2 единицы времени, ему потребуется столько же времени, сколько на "первый шаг", да еще два раза по столько же (Kj + 2*Kj), чтобы выполнять его за Tj-3 единиц времени - ((Kj + 2*Kj) + 3*Kj) и т.д. Чтобы научиться выполнять дело #j за Tj-M единиц времени, уже умея выполнять его за Tj-(M-1) единиц времени, Елисею потребуется в M раз больше времени, чем он затратил на приобретение умения выполнять дело за Tj-1 единиц времени.
Выполнять любое дело быстрее, чем за единицу времени, Елисей не может. Все навыки Елисей совершенствует параллельно.
Он хотел бы знать, через сколько дней общее время, в течение которого он исполняет государственные дела, уменьшится на R единиц времени, если, конечно, это возможно.
 
Формат входного файла input.txt
Первая строка - целые числа N (1 <= N <= 100) и R (0 <= R <= 10000)
Вторая строка - целые числа T1, T2, ..., TN (1 <= Tj <= 10000, j = 1, 2, ..., N) через пробел - количество единиц времени, которое Елисей затрачивает в настоящий момент на каждое из N государственных дел.
Третья строка - целые числа K1, K2, ..., KN (1 <= Kj <= 1000, j = 1, 2, ..., N) через пробел - количество дней, в течение которых Елисей может научиться выполнять дело #j за Tj-1 единицу времени

Формат выходного файла output.txt
Первая строка - целое число - минимальное количество дней, через которое Елисей будет тратить на государственные дела на R единиц времени меньше, или слово NO, если это невозможно
Вторая строка (присутствует в выходном файле, если освободить R единиц времени возможно) - целое число - количество дел, которые Елисей к этому времени будет выполнять ровно за одну единицу времени. 

Пример входного файла:
3 9
10 7 8
2 3 1

Пример выходного файла:
12
0

Сдать задачу

Задать вопрос жюри по этой задаче