Water
Турнир за Купата на Декана, 2014
Time Limit: 0.5s, Memory Limit: 64MiB
Докато кодът й се компилира, Ели се забавлява по следния начин. Пред нея има N на брой чаши с еднаква вместимост. Всяка от чашите съдържа определено количество вода в себе си. Момичето взима най-пълната чаша, която може да се излее изцяло в друга чаша, без втората да прелее, и прави това. Ако Ели има избор между няколко чаши, в които би могла да излее най-пълната чаша, тя избира най-пълната измежду тях.

Сега Ели се чуди каква трябва да е вместимостта на чашите, така че в крайна сметка да събере цялата вода в не повече от K чаши, изпълнявайки гореописаните действия?
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа N и K – съответно броя чаши, които има на масата, и максималния брой чаши, в които Ели би желала да събере цялата вода. На втория ред са зададени N на брой цели числа Ai – количеството вода във всяка от чашите в началото.
Изход
На стандартния изход изведете едно цяло число – минималната вместимост на чашите, с която Ели, прилагайки гореописаната операция, би събрала цялата вода в K или по-малко чаши.
Ограничения
  • 1 ≤ N, K, Ai ≤ 2000
Примерен Вход Примерен Изход
5 3 7 1 5 3 5 8
8 2 2 3 5 15 13 30 2 8 40
10 4 13 42 666 543 123 714 1 397 512 76 909
В първия пример, ако вместимостта на чашите е 8, то Ели би изсипала първо тази с 7 милилитра в тази с 1 милилитър, после някоя от 5-ците в тази с 3. Така в крайна сметка остават 3 пълни чаши – две с по 8 милилитра, и една с 5.
Във втория пример забележете, че при друга стратегия на изсипване водата би се побрала в две чаши дори ако имаха вместимост 39 милилитра, но следвайки процедурата на Ели изисква 40.
Мрън!