Sysadmin
Дизайн и Анализ на Алгоритми, 2011
Time Limit: 0.1s, Memory Limit: 64MiB
Обир на банка. Един от маскираните обирджии говори по телефона:
- "Шефе, проникнахме в банката, взехме заложници, срязахме кабЕЛИте за тока, започнахме да разбиваме сейфа... обаче през вентилацията се появи брадясал мъж със захабени дрехи, обезвреди ни, взе ни резачките и оръжията..."
- "И какво, освободи заложниците?"
- "А, не, почна да лепи кабелите и да мърмори нещо за "uptime"."
- "Ясно. Имаме си работа със сисадмин..."

Работата на системния администратор изобщо не е толкова лесна. Обирджиите са нарязали кабелите на N парчета с дължини A1, A2, ..., AN. За да възстанови връзката на всички компютри, на него са му нужни K парчета кабел с еднаква дължина. Затова той иска да нареже намиращите му се под ръка N парчета на (евентуално) по-малки такива, така че да има К парчета кабел с еднаква дължина. Разбира се, колкото по-дълги са тези К парчета, толкова по-добре.
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа N и K – съответно броя парчета, които са оставили обирджиите, и броя парчета с еднаква дължина, от които се нуждае сисадминът. На втория ще бъдат зададени N цели числа A1, A2, ..., AN, разделени с интервали – дължините на оставените от обирджиите парчета.
Изход
На стандартния изход изведете един ред – максималната целочислена дължина, с която сисадминът може да изреже К кабела с еднаква дължина. Ако това е невъзможно дори при дължина едно, изведете 0.
Ограничения
  • 1 ≤ N ≤ 100,000
  • 1 ≤ K ≤ 1,000,000,000
  • 1 ≤ Ai ≤ 1,000,000,000
Примерен Вход Примерен Изход
3 4 5 3 5 2
5 42 1 2 3 4 5 0
11 42 33 17 42 13 7 5 23 20 1 18 6 4
В първия пример обирджиите са оставили три парчета с дължини, съответно, 5, 3, и 5. Сисадминът иска да направи от тях четири с еднаква дължина. Те не могат да бъдат с дължина по-голяма от две, тъй като, например, с дължина три можем да изрежем най-много едно от първото парче, едно от второто и едно от третото, общо получавайки три парчета. В третия пример можем да изрежем точно 42 парчета с дължина 4.
Мрън!