Что может быть лучше воппера? Только двойной воппер! А что насчёт $$$k$$$-ного воппера? Боб захотел нажраться как свинья, но Алиса хочет ему помешать!

В «Бургер Кинге» провели реформу, и теперь там есть $$$n$$$ касс, пронумерованных от $$$0$$$ до $$$n - 1$$$. Для каждой кассы заданы два числа: $$$a_i$$$ и $$$k_i$$$ — соответственно изменение количества котлет в воппере при посещении этой кассы и её важность. Значение $$$a_i$$$ может быть отрицательным, тогда количество котлет уменьшается.

Все посетители начинают путь с кассы $$$n - 1$$$ и затем переходят между кассами, пока не дойдут до кассы $$$0$$$. Находясь в кассе с номером $$$i$$$ ($$$0 \lt i \lt n$$$), можно перейти либо в кассу с номером $$$i - 1$$$, либо выбрать число $$$b$$$ ($$$1 \lt b \le k_i$$$) и перейти в кассу с номером $$$\lfloor i / b \rfloor$$$.

До посещения кассы $$$n-1$$$ в воппере Боба содержится $$$10^{100}$$$ котлет (вы думали, мы блефовали в первом абзаце?). При посещении кассы с номером $$$i$$$ к вопперу обязательно добавляется $$$a_i$$$ котлет, не взять котлеты нельзя. Алиса и Боб ходят по очереди, причём Алиса ходит первой. Алиса стремится минимизировать итоговое количество котлет, а Боб — максимизировать его. Во время своего Алиса или Боб выбирают следующую кассу, в которую они перейдут.

Определите, сколько котлет будет в воппере при оптимальной игре обоих игроков.

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