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

После долгих прений жюри утвердило регламент проведения соревнований. Соревнования длятся \(m\) дней. Всем участникам выдаются одинаковые грядки с \(n\) ростками бамбука. В момент начала соревнований — 5:00 первого дня — высота \(i\)-го ростка на грядке каждого участника равна \(a_i\) . Каждую полночь \(i\)-й росток вырастает на \(b_i\) . Утром каждого дня, начиная с первого, ровно в 6:00, каждый участник может один раз постричь бамбук на своей грядке. Происходит это так: участник выбирает \(i\) и \(j\) \((1 \le i \le j \le n)\) — левую и правую границу отрезка ростков, которые он хочет постричь, затем выбирает высоту \(l \ (0 \le l \le 2 \cdot 10^9\) ), и все ростки, с \(i\)-го по \(j\)-й включительно, высота которых больше \(l\), обрезаются до высоты \(l\). Сравнение работ происходит в полдень \(m\)-го дня. Победителями соревнований считаются те участники, которые, сделав минимальное количество стрижек, смогли получить грядку, все \(n\) ростков на которой имеют высоту \(h\).

Теперь жюри интересно, какое минимальное число раз победителю придется стричь бамбук.

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

Обычно внизу каждой страницы условий есть надпись вида «Страница \(i\) из \(n\)», где \(i\) — номер страницы условий, а \(n\) — количество страниц в условиях. Однако на этом листе была всего одна длинная последовательность цифр. Видимо, принтер почему-то не напечатал ни одного символа кроме цифр. Таким образом, номера \(i\) и \(n\) слились в единую последовательность цифр.

Теперь понять, какой же был номер у найденной страницы, стало большой проблемой, и решений у этой задачи может быть много. Роботу стало интересно, сколько существует решений, но так как робот не предназначен для решения таких задач, он нуждается в вашей помощи. Страницы в условиях нумеруются от \(1\) до \(n\), числа \(i\) и \(n\) записываются без ведущих нулей.

Выясните, сколько есть корректных надписей вида «Страница \(i\) из \(n\)», при удалении из которых всех символов кроме цифр получается заданная во входном файле строка

Многим из вас, наверное, известна легенда про Ханойскую башню. Легенда гласит, что в одном далеком монастыре находится бронзовый диск, на котором закреплены три алмазных стержня. Давным-давно, в самом начале времен, монахи этого монастыря провинились перед богами. Разгневанные боги положили \(n\) дисков на один из стержней, все диски имели разные радиусы и были расположены по убыванию радиуса — самый большой диск лежал снизу, на нем диск поменьше, \(\dots\) , самый маленький диск располагался сверху. Монахи должны перекладывать диски между стержнями, причем каждый раз должны класть диск либо на пустой стержень, либо поверх большего диска. Как только все \(n\) дисков будут переложены со стержня, на который боги сложили их, на другой стержень, башня вместе с храмом обратятся в пыль и под громовые раскаты погибнет мир.

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

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

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

Первокурсник Макс только что решил с головой погрузиться в учебу. К завтрашнему семинару по мифологии ему необходимо подготовить доклад в \(k\) страниц. Макс любит мифологию, так что доклад уже готов, осталось только его распечатать.

К сожалению, во всех имеющихся в общежитии принтерах закончились картриджи, и теперь Максу придется купить новые картриджи для печати доклада. В магазине обнаружилось \(n\) типов картриджей. Продавец объяснил Максу, что картридж имеет два основных параметра — стоимость и количество страниц, на печать которых его хватает.

Выяснилось, что картридж \(i\)-го типа стоит \(c_i\) рублей и может напечатать \(p_i\) страниц. В магазине есть в наличии неограниченное количество картриджей каждого типа.

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

Поэтому Макс хочет купить картриджей с минимальной суммарной стоимостью, которых достаточно для печати ровно \(k\) страниц.

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

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

Опишем суть этой структуры данных. Квадродерево позволяет нам представлять в памяти таблицу размера \(2^n \times 2^n\) , состоящую из нулей и единиц. Все дерево состоит из ячеек, каждая ячейка отвечает за некоторую часть этой таблицы, при этом каждая часть является квадратом со стороной \(2^p\) . Первая ячейка отвечает за всю таблицу.

Если все элементы квадрата, за который отвечает ячейка, имеют одинаковое значение (\(0\) или \(1\)), то в ячейке просто хранится эта информация. Если же внутри квадрата существуют хотя бы два различных элемента, то весь квадрат делится на четыре непересекающихся квадрата со стороной \(2^{p−1}\) , после чего для каждой четверти создается отдельная ячейка, и ссылки на все четыре созданных ячейки записываются в ячейку, отвечающую за большой квадрат.

Правильное квадродерево для данной таблицы. Любой квадрат, у которого все четыре стороны выделены, является ячейкой квадродерева. Всего используется \(13\) ячеек.

Выясните, какое минимальное возможное количество ячеек может быть в квадродереве, описывающем таблицу, получающуюся из данной изменением не более, чем \(k\) элементов.