Василий мечтает стать программистом k-го уровня. У него есть n дней чтобы осуществить задуманное — повысить свой уровень с 1-го до k-го. Для перехода с уровня x на уровень x + 1 необходимо с момента получения уровня x решить x задач.

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

Решённые задачи не накапливаются при переходе на следующий уровень, то есть для каждого x для перехода на уровень x + 1 Василию надо решить x задач, именно будучи программистом уровня x.

Василий может приступить к занятиям в любой день от 1 до n, при этом он хочет минимизировать разницу между номером дня, когда он станет программистом k-го уровня, и днём, когда он начнёт заниматься.

Иван очень любит читать газеты, особенно ему интересны политические новости и новости спорта. Также у Ивана есть любимая строка s.

У Ивана очень много свободного времени, да и читает он очень быстро, а вот газет, которые ему интересны, за день выходит не так много. Поэтому в последнее время после прочтения очередной газеты Иван стал считать количество вхождений своей любимой строки s в текст t, написанный в газете, в качестве подстроки. Подстрокой строки x называется последовательность подряд идущих символов строки x.

Но вскоре и с подсчётом вхождений Иван стал справляться очень быстро, и он решил после прочтения очередной газеты заменить в своей любимой строке не более k символов таким образом, чтобы максимизировать количество вхождений изменённой строки s в текст газеты t.

Перед вами стоит задача помочь Ивану и посчитать максимальное количество вхождений его любимой строки s после замены в ней не более k символов в текст газеты t. Ивану не обязательно заменять ровно k букв, и, возможно, ему даже не придётся заменять ни одной буквы. Заменять букву из строки s можно на любую другую.

Компания ХакерКук провела свой грандиозный чемпионат по спортивному программированию с большим призовым фондом, однако распределение призовых денег до сих пор не объявлено. Единственное, что известно об итоговом распределении, это что участник с более высоким местом получит не меньше призовых денег, чем участник с более низким местом.

Теперь один работник ХакерКук хочет распределить призовой фонд так, чтобы его друзья суммарно получили как можно больше денег. Определите, какую часть призового фонда получит каждый из участников при условии, что работник распределит деньги оптимально.

Вася хочет подарить Маше букет на 8 марта. Он знает одну тайную тропинку в лесу за городом, вдоль которой растут красивые, а главное, бесплатные цветы. Тропинка может быть представлена как прямая, причём можно считать, что Вася изначально появляется на ней в точке 0 и двигается со скоростью 1, не затрачивая времени на то, чтобы срывать цветы.

Цветок номер i растёт в точке тропинки с координатой x_i, а после того, как Вася его сорвёт, цветок остается живым еще t_i единиц времени. Естественно, Вася должен набрать в букет нечётное число цветов, и все они должны быть живыми в момент, когда он принесёт их в точку 0 на встречу с Машей (если i-й цветок принести ровно через t_i единиц времени после его срывания, то он уже не считается живым).

Вася — человек прямой, и даже ради Маши он не готов поворачивать (то есть менять направление своего движения вдоль тропинки) более 2 раз. Помогите ему собрать самый большой букет нечётного размера.

В чемпионате Берляндской хоккейной лиги участвуют n команд. Турнир проходит по круговой системе: каждая команда играет с каждой ровно один матч, при этом ничьих в турнире не бывает. В отличие от традиционных турниров, распределение призов в Берляндской хоккейной лиге зависит не от итогового места команды, а от количества побед. А именно: призы получают все команды, выигравшие как минимум w игр. Хоккейный эксперт Дон Берри интересуется, могут ли по итогам этого турнира получить призы ровно k команд. Если такой турнир существует, вам нужно вывести победителя для каждого матча.

Прошло 20 лет. Карлсон располнел и больше не летает. Малыш устроился на работу, стал топ-менеджером и теперь живёт в огромном доме на n-м этаже.

Карлсон решил пойти в гости к Малышу. Разумеется, пешком подниматься он не собирается, поэтому на первом этаже Карлсон заходит в лифт.

Кнопки в лифте расположены снизу вверх таким образом, что человек с ростом h может достать до любой кнопки, соответствующей этажу от 1 до h включительно. При этом на i-м этаже у Карлсона есть друг с ростом h_i, и его можно попросить нажать на любую кнопку, до которой он может дотянуться. Разумеется, чтобы попросить друга с i-го этажа нажать на кнопку, сначала нужно оказаться на этаже i. Карслон хочет добраться до Малыша, обратившись за помощью к минимально возможному количеству друзей.

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

Петя и Вася играют в известную игру «Камень-ножницы-бумага». Игра проходит в n раундов. В каждом раунде Петя и Вася выбирают одну из трёх фигур: камень, ножницы или бумагу. Если фигуры игроков не совпали, победитель определяется стандартным способом (камень побеждает ножницы, ножницы побеждают бумагу, бумага побеждает камень), иначе объявляется ничья. За победу присуждается w очков, за ничью — d очков, за поражение — 0 очков. Итоговый счёт каждого игрока — это сумма очков по всем раундам.

Петя заранее определил, какую фигуру он будет выбирать в каждом раунде, и записал это в виде строки длины n из букв «r», «s» и «p». Здесь буква «r» на i-й позиции в строке означает, что в i-м раунде Петя выберет камень, «s» — ножницы, а «p» — бумагу.

Вася заполучил некоторый циклический сдвиг строки Пети и хочет воспользоваться этой информацией, чтобы максимизировать свой итоговый счёт. Найдите максимальный счёт, который может гарантировать себе Вася вне зависимости от того, каким именно циклическим сдвигом исходной строки является строка, известная Васе.