Кондитер приготовил длинную плитку, состоящую из n подряд идущих долек. Сладость i-й дольки равна a_i.

Нужно сделать ровно k разрезов между соседними дольками, чтобы получить k+1 непустой кусок, каждый из которых состоит из подряд идущих долек.

Сладость куска равна сумме сладостей всех долек в этом куске. Кондитер хочет выполнить разрезы так, чтобы самый маленький по сладости кусок оказался как можно слаще.

Требуется определить максимально возможную сладость минимального куска.

Входные данные

В первой строке заданы два целых числа n и k — количество долек в плитке и количество разрезов соответственно.

Во второй строке заданы n целых чисел a_i — сладости долек.

Выходные данные

Выведите одно целое число — максимально возможную сладость самого маленького из полученных кусков.

Ограничения

• 0 <= k < n <= 2 * 10^5
• 1 <= a_i <= 10^9

Примеры

Пример 1

Входные данные

1 0
1

Выходные данные

1

Пример 2

Входные данные

5 2
1 2 3 4 5

Выходные данные

4