В игре нужно собрать древесину для строительства домика. Рядом растут N деревьев. Высота дерева с номером i равна Ai метрам.
Игрок выбирает одну целую неотрицательную высоту среза H для всех деревьев. У каждого дерева выше H срезается верхняя часть. Её длина добавляется к запасу древесины. Деревья высотой не больше H остаются без изменений.
Например, при высоте среза 6 м дерево высотой 10 м даст 4 м древесины, а дерево высотой 5 м не даст древесины.
Для домика нужно не менее K метров древесины. Найдите наибольшую высоту среза, при которой удастся собрать нужное количество.
Входные данные
В первой строке записаны два целых числа N K — количество деревьев и необходимая суммарная длина срезанных частей.
Во второй строке записаны N целых чисел A1, A2, …, AN — высоты деревьев.
1 ≤ N ≤ 1000; 1 ≤ Ai ≤ 109; 1 ≤ K ≤ A1 + A2 + … + AN.
При высоте среза 0 древесины всегда достаточно.
Выходные данные
Выведите одно целое число — максимальную высоту среза в метрах.
| № | Входные данные | Выходные данные |
|
1
|
4 7
20 15 10 17
|
15
|
|
2
|
3 6
1 2 3
|
0
|