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

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

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

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

(Задача отличается от предыдущых исключительно ограничениями.)

Есть сообщение, записанное в алфавите из N символов. Известно, что 1-й, 2-й, ..., N -й символы алфавита использованы в сообщении f ₁ , f ₂ , ..., f _N раз. Его необходимо набрать на M -клавишной клавиатуре, используя способ набора, аналогичный используемому в мобильных телефонах.

На телефоне, клавише 2 сопоставлены буквы abc, клавише 3 — def, и т.д. Для набора текста телефон переводится в специальный режим, в котором одно нажатие на клавишу 2 порождает символ a, 2 подряд нажатия на 2 символ b, 3 подряд символ c; аналогично, одно нажатие 3 порождает d, 2 подряд e и т. д. Если же необходимо набрать 2 подряд буквы a, то нажимают клавишу 2, немного ждут и снова нажимают клавишу 2.

В нашем случае, символы с 1-ого по некоторый K ₁ -ый должны соответствовать 1-ой клавише, с ( K ₁ + 1) -ого по некоторый K ₂ -ой — 2-ой клавише и т. д., до K _M = N . Конкретные значения K ₁ , K ₂ , ..., K _{M - 1} не задаются — их, наоборот, нужно подобрать.

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

(Задача отличается от предыдущых исключительно ограничениями.)

Есть сообщение, записанное в алфавите из N символов. Известно, что 1-й, 2-й, ..., N -й символы алфавита использованы в сообщении f ₁ , f ₂ , ..., f _N раз. Его необходимо набрать на M -клавишной клавиатуре, используя способ набора, аналогичный используемому в мобильных телефонах.

На телефоне, клавише 2 сопоставлены буквы abc, клавише 3 — def, и т.д. Для набора текста телефон переводится в специальный режим, в котором одно нажатие на клавишу 2 порождает символ a, 2 подряд нажатия на 2 символ b, 3 подряд символ c; аналогично, одно нажатие 3 порождает d, 2 подряд e и т. д. Если же необходимо набрать 2 подряд буквы a, то нажимают клавишу 2, немного ждут и снова нажимают клавишу 2.

В нашем случае, символы с 1-ого по некоторый K ₁ -ый должны соответствовать 1-ой клавише, с ( K ₁ + 1) -ого по некоторый K ₂ -ой — 2-ой клавише и т. д., до K _M = N . Конкретные значения K ₁ , K ₂ , ..., K _{M - 1} не задаются — их, наоборот, нужно подобрать.

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

Ориентированный взвешенный граф задан перечнем дуг (ориентированных рёбер). Отсортировать эти дуги по возрастанию длин, сохранив (в дополнительных полях) номера этих дуг во входных данных.

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

Поле для выполнения задания представляет собой прямоугольник размером \(n \times m\) метров, разбитый на квадраты единичной площади. В одном из квадратов исходно находится Артур, в некотором другом квадрате находится котенок. Кроме того, один из квадратов содержит лифт, встав на который вместе с котенком, Артур успешно выполняет задание.

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

Выяснив, сколько шагов ему придется сделать, Артур заинтересовался, сколько существует различных способов дойти до котенка, а затем с ним до лифта, сделав в сумме минимальное число шагов. Помогите ему это выяснить. Это число может быть довольно большим, поэтому Артур просит найти его по модулю \(10^9+7\).