Разделите положительный массив на не более k непустых непрерывных блоков. Минимизируйте максимальную сумму блока.

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

В первой строке n. Во второй — n целых чисел a[i]. В третьей строке k.

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

Минимально возможная максимальная сумма.

Ограничения

1 ≤ n ≤ 100000; 1 ≤ a[i] ≤ 10^9; 1 ≤ k ≤ n.

Пример 1

Ввод:

Вывод:

Пример 2

Ввод:

Вывод: