У Васи есть хор из $$$n$$$ хомяков. Каждый хомяк поёт с громкостью 2, 3, 4 и 5. Однако, если объединить $$$k$$$ хомяков в группу, то они все начнут петь с громкостью $$$\max(2, max - (k - 1))$$$, где $$$max$$$ — самая большая громкость голоса в группе.

Вася хочет объединить некоторых хомяков в группы (остальные при этом могут остаться петь поодиночке) так, чтобы суммарная громкость (то есть сумма громкостей голосов хомяков) была максимальной.

В штаб-квартире корпорации «Айсберг» работает множество пингвинов. Здание корпорации состоит из $$$n$$$ этажей, пронумерованных от $$$1$$$ до $$$n$$$.

Сегодня $$$k$$$ пингвинов хотят переместиться по зданию. Известно, что $$$i$$$-й пингвин находится на этаже $$$s_i$$$ и хочет попасть на этаж $$$f_i$$$. Так как пингвины не любят спускаться, гарантируется, что все они едут только вверх ($$$s_i \lt f_i$$$).

В здании есть ровно один ультрасовременный лифт, который изначально находится на $$$1$$$-м этаже. Его вместимость не ограничена. Лифт потребляет энергию по следующим правилам:

• Перемещение лифта на один этаж вверх или вниз тратит $$$1$$$ единицу энергии.
• Остановка на этаже (чтобы открыть и закрыть двери для посадки или высадки пингвинов) тратит $$$2$$$ единицы энергии. Лифт тратит эту энергию только в том случае, если на этаже действительно кто-то заходит или выходит.

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

В Долине Медленных Шагов черепашки записывают на панцире длинные числа. Иногда некоторые цифры стираются, и на их месте появляется символ ?. Черепашки хотят восстановить число так, чтобы оно делилось на $$$3$$$.

Вам дана строка $$$s$$$ длины $$$n$$$, состоящая из цифр 0–9 и символов ?. Требуется заменить каждый символ ? на одну из цифр 0–9 так, чтобы получившееся число:

• не имело ведущих нулей (то есть при $$$n \gt 1$$$ первая цифра не равна 0);
• делилось на $$$3$$$.

Среди всех подходящих чисел нужно вывести минимальное по величине.

Если восстановить число невозможно, выведите -1.

Зима уже закончилась, но Егор не собирается бросать своё хобби — лепку снеговиков. Он заготовил $$$n$$$ снежных комьев и для каждого комка определил его размер — $$$a_i$$$. Как не бывает двух абсолютно одинаковых снежинок, так и не бывает двух одинаковых снежных кома, даже если они одинакового размера. Поэтому будем считать, что все комья снега различны.

По мнению Егора, снеговик должен состоять ровно из трёх комьев, причём на каждом коме могут стоять только строго меньшие его по размеру. Теперь Егор хочет узнать, сколькими способами он может слепить снеговика из снежных заготовок.

В Долине Больших Луж капибары каждый вечер играют в «три в ряд» на бесконечном клетчатом поле. В некоторых клетках уже лежат камешки-метки (крестики). Капибары хотят сделать ровно один дополнительный ход: поставить метку в одну клетку так, чтобы после этого на поле появилась тройка меток подряд по одной из линий: по горизонтали, по вертикали или по диагонали.

Вам даны координаты $$$n$$$ клеток, в которых уже стоят метки. Гарантируется, что изначально на поле нет ни одной тройки подряд (по горизонтали, вертикали или диагонали). Требуется посчитать, сколькими способами можно выбрать одну клетку для постановки новой метки так, чтобы тройка подряд появилась.

В городе Котофф живут котики, которые очень любят ходить в гости и соблюдать правила дорожного движения. Все дорожки в городе имеют направление движения и у каждой дорожки установлен светофор. Начинать движение по дорожке можно, только если светофор горит зелёным. Каждый светофор чередует сигналы: $$$r_i$$$ секунд горит красный, после чего $$$g_i$$$ секунд горит зелёный, затем процесс повторяется. Ещё известно, что от домика $$$a_i$$$ к домику $$$b_i$$$ можно пройти за $$$t_i$$$ секунд.

Котик А живёт в домике $$$1$$$, и собрался в гости к котику B, который живёт в домике $$$n$$$.

По магическому стечению обстоятельств, в момент времени, когда котик А вышел из дома, все светофоры города загорелись красным.

Помогите котику А посчитать, за какое время он сможет добраться до котика В.

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

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

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

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

Локации пронумерованы целыми числами от $$$1$$$ до $$$n$$$. Всего существует $$$m$$$ направленных тропинок. $$$i$$$-я тропинка имеет вид ($$$x_i, y_i$$$), что означает наличие направленной тропинки из локации $$$x_i$$$ в локацию $$$y_i$$$.

Валера хочет выбрать четыре различных тропинки $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$, такие что если пройти по тропинкам $$$a \rightarrow b \rightarrow c \rightarrow d$$$, получится замкнутый маршрут длины $$$4$$$. Тропинки считаются различными по их индексам, даже если они соединяют одни и те же локации.

Помогите Валере узнать, сколько существует допустимых четвёрок тропинок ($$$a, b, c, d$$$).

Как вы знаете, выдры очень любят камешки. Некоторые выдры выбирают себе один камешек на всю жизнь, но Оттервер не из таких. У него есть рюкзак, который вмещает $$$W$$$ килограммов. В его распоряжении есть 3 типа камешков, каждый тип характеризуется своим весом и своей значимостью. Камешки каждого типа он может брать в неограниченном количестве (естественно, взятые камешки должны влезать в рюкзак). Оттервер хочет набрать в рюкзак камешков так, чтобы они имели максимальную суммарную значимость. К сожалению, так как выдры в этой задаче гигантские, то и рюкзак, и камешки соответствующих размеров. Помогите ему с этой сложной задачей, ведь он всего лишь бедный выдр!

Тюлень по имени Блинчик учится в первом классе звериной школы, и сегодня проходит урок рисования на его любимую тему — ученики будут рисовать морских обитателей. Учительница задала Блинчику нарисовать картину, на которой плавают ровно $$$m$$$ рыб. У Блинчика есть $$$n$$$ разноцветных карандашей, которыми он может рисовать рыб. Для каждой рыбы $$$X$$$ на картине, если она нарисована карандашом цвета $$$i$$$, то за неё учительница поставит Блинчику в дневник $$$a_i - k_X$$$ звёздочек, где $$$k_X$$$ — количество рыб цвета $$$i$$$, кроме $$$X$$$, а если $$$a_i \lt k_X$$$, то учительница не примет работу.

Помогите Блинчику получить как можно больше звёздочек в дневнике.

После выполнения зарядки (см. задачу отбора «Зарядка для хомяков») все $$$n$$$ хомяков выстроились по росту и были пронумерованы числами от $$$1$$$ до $$$n$$$ в порядке увеличения роста (хомяк номер 1 имеет наименьший рост, номер $$$n$$$ — наибольший рост), при этом оказалось, что все хомяки имеют разный рост. После этого было проведено взвешивание и удалось установить веса всех хомяков, для каждого $$$i$$$ известно значение $$$a_i$$$ — вес хомяка с номером $$$i$$$.

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

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

Разумеется, ведущий хомяк хочет, чтобы после этого максимальный размер гармоничного отряда не изменился (иначе его расчеты окажутся неверными). Посчитайте, сколькими способами можно выбрать непустую группу хомяков для подготовки олимпиады, чтобы из оставшихся хомяков можно было сформировать гармоничный отряд размера $$$m$$$. Кстати, число $$$m$$$ ведущий хомяк вам не сказал.