Входной файл: Input.txt

Выходной файл: Output.txt

Ограничение времени: 1 секунда

Ограничение памяти: 64 М байт

В романе N глав (N ≤ 100). В i-ой главе A_i страниц. Требуется издать роман в K томах (1 < K < N) так, чтобы объем самого толстого тома был минимален. Делить и переставлять главы нельзя.

Вход

Во входном файле записаны целые числа N, K, A₁, A₂, ..., A_N в указанном порядке. Количество страниц в романе не превосходит 2∙10⁹.

Выход

В выходной файл запишите количество страниц в самом толстом томе.

Пример входа и выхода

Задача 4. "Игроки"

Входной файл: Input.txt

Выходной файл: Output.txt

Ограничение времени: 1 секунда

Ограничение памяти: 64 М байт

Фишки разложили в стопки (в разных стопках может быть различное количество фишек), а стопки расположили на столе в ряд слева направо. Два игрока по очереди делают ходы: один из игроков берет слева несколько стопок, не меньше одной, но и не больше, чем перед этим взял его соперник. Первый игрок своим первым ходом берет не более К стопок. Игра заканчивается, когда стопок не остается. Требуется написать программу для вычисления, какое максимальное число фишек может накопить первый участник после окончания игры, если второй тоже старается ходить так, чтобы получить как можно больше фишек.

Вход

Входной файл состоит из одной строки, в которой записаны: число стопок N (1 ≤ N ≤ 180), за ним идут N чисел, задающих количество фишек в стопках слева направо (количество фишек в стопке - не менее 1 и не более 20000), а затем число К, ограничивающее количество стопок, которые первый игрок может взять на первом ходе (1 ≤ К ≤ 80). Все числа в строке разделены пробелом.

Выход

В выходной файл необходимо вывести одно число - максимальное количество фишек, которое заведомо может получить первый игрок.

Пример входа и выхода

Задача 5. "Признак делимости на K"