Розподіл виборчих урн
Сьогодні, окрім 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 і не повинен оброблятися.
Вихідні дані
Для кожного випадку ваша програма повинна вивести одне ціле число, максимальну кількість людей, призначених для однієї урни у найефективнішому розподілі.