Никита известен тем, что он отлично знает школьную программу по математике и умеет решать линейные уравнения любого уровня сложности. Для того, чтобы заинтересовать юного математика, учитель написал на доске два целых числа $$$a$$$ и $$$b$$$ и дал школьнику следующую задачу.

Учитель разрешил Никите не более, чем $$$k$$$ раз выполнить одно из следующих действий:

1. Увеличить число $$$a$$$ на единицу;
2. Увеличить число $$$b$$$ на единицу.

Задача Никиты — выполнить разрешенные действия таким образом, чтобы максимизировать произведение двух полученных чисел. К сожалению, решить данную задачу самостоятельно школьнику не удалось, поэтому вам придется ему помочь.

Помимо тестов из условия, данная задача содержит 25 тестов, каждый из которых будет независимо оцениваться в 4 балла.

Одна известная команда впервые за несколько месяцев решила написать тренировку. Но друзья решили, что им чужды старые технологии, поэтому они попросили нейросеть сгенерировать задачу, а потом решить ее (ведь зачем решать задачи самим). Сама задача звучала довольно просто.

Вам даны $$$n$$$ строк $$$s_1, s_2, \ldots, s_n$$$, состоящих из цифр от $$$0$$$ до $$$9$$$. Необходимо посчитать количество пар индексов $$$(i, j)$$$ $$$1 \le i \lt j \le n$$$, таких что строка $$$s_i + s_j$$$ является хорошей, где $$$s_i + s_j$$$ — это конкатенация строк $$$s_i$$$ и $$$s_j$$$. Строка $$$t$$$ длины $$$m$$$ называется хорошей, если для любого индекса $$$1 \lt i \le m$$$ выполнено неравенство $$$t_{i - 1} \le t_i$$$.

Сгенерировать задачу нейросеть смогла, а вот решить ее — нет. Но друзья уже очень устали, поэтому решать эту задачу придется вам.

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

Обозначим за $$$m$$$ сумму длин всех строк $$$s_i$$$. Иными словами, $$$m = \sum \limits_{i=1}^{n} \lvert s_i \rvert$$$.

Недавно Миша увлекся разработкой игр и уже выпустил свою первую игру в жанре RPG «Надземелья и Дарконы». Вы играете за рыцаря, который побеждает дарконов в надземельях. Все надземелья сгенерированы процедурно, драки с дарконами детально проработаны, а умопомрачительной 3D-графике позавидует даже «Суперпанк»!

Даня уже давно занимается прохождением игр на скорость, за что он и получил свою известность в сети Интернет. Миша обратился к Дане за помощью: он хочет, чтобы Даня во время прямой трансляции прошел игру «Надземелья и Дарконы» как можно быстрее, так как думает, что это привлечет новых игроков. Даня не смог отказаться от очередного испытания, однако быстрое прохождение требует глубоких знаний об игре, а времени на изучение у него нет, так что Миша вкратце объяснил, в чем заключается суть игры.

Ваш персонаж начинает свой путь с уровнем силы $$$x$$$. Он может пойти в любое из $$$n$$$ надземелий, пронумерованных целыми числами от $$$1$$$ до $$$n$$$, и попытаться победить там даркона, за счет чего повысить свой уровень. А именно, в надземелье с номером $$$i$$$ живет даркон с уровнем силы $$$a_i$$$, и его можно победить только в том случае, если уровень силы вашего персонажа больше уровня силы даркона. В противном случае вы гарантировано проиграете. После победы над дарконом уровень персонажа повысится на $$$a_i$$$, а само надземелье станет зачищенным, то есть там больше не будут появляться дарконы. Целью игры является победить самого большого и страшного даркона, живущего в надземелье под номером $$$n$$$, поэтому вы должны сражаться с дарконами, пока не получите достаточный уровень силы и не победите финального босса.

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

Найдите оптимальную стратегию или скажите, что игру пройти невозможно.

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

В результате неудачного стечения обстоятельств Миша оказался на необитаемом острове. Первым делом он, разумеется, выложил из камней большую надпись S.O.S. на пляже. Однако, до прибытия помощи ему нужно чем-то развлечься, поэтому он решил поиграть с оставшимся камнями.

Миша выложил все оставшиеся у него камни в $$$n$$$ кучек таким образом, что в $$$i$$$-й кучке оказалось ровно $$$r_i$$$ камней. После этого мальчик решил взять из каждой кучки некоторое количество камней, чтобы были выполнены следующие условия:

• Из $$$i$$$-й кучки Миша должен взять не менее, чем $$$l_i$$$ и не более, чем $$$r_i$$$ камней;
• Суммарное количество взятых камней должно быть равно $$$s$$$.

После того, как Миша справился с данным заданием он задумался, сколькими способами он может взять камни из кучек таким образом, чтобы описанные условия были выполнены. А именно, для каждой кучки $$$i$$$ он хочет вычислить, сколькими способами он может выбрать некоторое количество камней из $$$i$$$-й кучки, чтобы из остальных кучек можно было выбрать некоторое количество камней, выполнив описанные условия.

К сожалению или к счастью, помощь прибыла слишком быстро, и Миша не успел найти ответ на свой вопрос. Поэтому сделать это предстоит вам.

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

Обозначим за $$$m$$$ максимальную разность между $$$r_i$$$ и $$$l_i$$$. Иными словами, $$$m = \max \limits_{i=1}^{n} (r_i - l_i)$$$.

В ряд стоят $$$n$$$ столбиков, пронумерованных слева направо целыми числами от $$$1$$$ до $$$n$$$. Высота $$$i$$$-го столбика равна $$$a_i$$$. Кузнечик может прыгать по столбикам только вперед (со столбика с меньшим номером на столбик с большим номером), и за один прыжок он может перепрыгнуть не более, чем на $$$k$$$ столбиков вперед. Формально, кузнечик может перепрыгнуть со столбика $$$i$$$ на столбик $$$j$$$, если $$$i \lt j$$$ и $$$j - i \le k$$$.

Кузнечик хочет быть как можно выше, поэтому он стремится максимизировать минимальную из высот посещенных им столбиков.

Обозначим за $$$f(l, r)$$$ максимум из минимальных высот посещенных столбиков по всем маршрутам кузнечика от столбика с номером $$$l$$$ до столбика с номером $$$r$$$.

Вам требуется найти значение суммы $$$\sum \limits_{l=1}^n \sum \limits_{r=l}^n f(l, r)$$$. Иными словами вы должны найти сумму значений $$$f(l, r)$$$ по всем парам столбиков $$$l$$$ и $$$r$$$ ($$$l \le r$$$).

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