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

В одной секретной игре, разрабатывающейся в недрах компании ZeptoLab, игровой мир представляет собой n уровней, расположенных по кругу. С i-го уровня можно попасть на уровни i - 1 и i + 1, при этом с уровня 1 можно попасть на уровень n и наоборот. Карта i-го уровня занимает объём в a_i байт.

В целях сокращения переданного трафика, игра получает уровни следущим образом. На сервере все уровни разбиты на m групп, и каждый раз, когда игрок впервые оказывается на одном из уровней очередной группы, сервер отправляет приложению все уровни этой группы единым пакетом. Таким образом, пока игрок путешествует внутри уровней одной группы, приложению не требуется никакой новой информации. В силу ограничений технического характера, пакет может содержать произвольное количество уровней, но суммарный размер описаний их карт не должен превосходить b байт, где b — некоторая положительная целая константа.

Игроки, как правило, проходят уровни один за другим, поэтому было принято решение разбить n уровней на m групп таким образом, чтобы каждая группа являлась сплошным отрезком, содержащим несколько соседних уровней (в том числе, группа может содержать два соседних уровня n и 1). В частности, если описания всех уровней суммарно весят не более b байт, то их всех можно объединить в одну грппу, чтобы отправить единым пакетом.

Определите, какое минимальное количество групп требуется образовать, чтобы организовать уровни игры, соблюдая указанные условия?

Так как разработка игры — длительный процесс, а технологии не стоят на месте, то пока невозможно точно предсказать, какое значение примет константа b, ограничивающая размер пакета. Поэтому разработчики просят вас определить ответ для нескольких значений b.