Распределение урн для голосования
Сегодня в Испании, помимо SWERC'11, проходит еще одно значимое событие — всеобщие выборы. Каждый житель страны в возрасте 18 лет и старше приглашен проголосовать, чтобы выбрать представителей в Конгресс депутатов и Сенат. Не беспокойтесь о том, что судьи могут покинуть свои посты, так как голосование не является обязательным.
Администрация располагает избирательными урнами, использовавшимися на прошлых выборах. К сожалению, человек, ответственный за распределение урн по городам, был уволен несколько месяцев назад из-за финансовых ограничений. В результате текущее распределение урн и списки избирателей в городах могут быть неэффективными. Ваша задача — продемонстрировать, насколько эффективно можно было бы организовать это распределение.
Единственное правило при распределении урн заключается в том, что каждому городу должна быть назначена хотя бы одна урна. Каждый избиратель должен голосовать в той урне, к которой он/она был(а) прикреплен(а) ранее. Ваша цель — минимизировать максимальное количество людей, назначенных для голосования в одной урне.
В первом примере ввода две урны распределяются в первый город, а остальные — во второй, и ровно 100000 человек голосуют в каждой из урн в наиболее эффективном распределении. Во втором примере 1, 2, 2 и 1 урны распределяются по городам, и 1700 человек из третьего города голосуют в каждой из двух урн, делая их самыми загруженными в оптимальном распределении.
Входные данные
Первая строка каждого тестового случая содержит два целых числа: N (1 ≤ N ≤ 500000), количество городов, и B (N ≤ B ≤ 2000000), количество избирательных урн. Каждая из следующих N строк содержит целое число a_i (1 ≤ a_{i} ≤ 5000000), обозначающее население i-го города.
После каждого случая будет включена одна пустая строка. Последняя строка ввода содержит -1 -1 и не должна обрабатываться.
Выходные данные
Для каждого случая ваша программа должна вывести одно целое число — максимальное количество людей, назначенных на одну урну в наиболее эффективном распределении.