Пачки для ассистентов

В школе готовят большой набор листков для контрольной. Листки идут в строгом порядке: сначала листок 1, потом 2, …, потом n.

Завуч хочет раздать работу k ассистентам так, чтобы каждый ассистент получил одну пачку подряд идущих листков (то есть листки каждого ассистента образуют отрезок по номерам), и все листки были розданы.

Если в пачке суммарно P страниц, то подготовка этой пачки занимает P минут. Ассистенты работают параллельно, поэтому общее время подготовки равно времени самой «долгой» пачки.

Нужно сделать раздачу так, чтобы это общее время было как можно меньше.

Формат ввода

В первой строке заданы два целых числа n и k — количество листков и количество ассистентов. Во второй строке задано n целых чисел a1, a2, …, an, где ai — число страниц в i-м листке.

Формат вывода

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

Ограничения

• 1 ≤ k ≤ n ≤ 200000
• 1 ≤ ai ≤ 10^9
• Ответ может не помещаться в 32-битный тип (используйте 64-битные значения; в Python ограничений нет).

Пример

Ввод:

5 2
10 1 1 1 10

Вывод:

12