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

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

После анализа дисков было установлено, что они использовались в XXI веке по летоисчислению, использовавшемуся древней цивилизацией — так называемому «григорианскому» календарю — год продолжительностью 365 дней, разделялся по нему на двенадцать месяцев. Второй месяц в году имел продолжительность двадцать восемь дней, первый, третий, пятый, седьмой, восьмой, десятый и двенадцатый — тридцать один день, остальные — тридцать дней. В особые года, номер которых делился на четыре и не делился на сто, либо делился на четыреста, второй месяц длился двадцать девять дней. Веком номер \(i\) назывался период с \(100 \cdot (i \ − \ 1) + 1\) года по \(100 \cdot i\).

Так как достоверно не известно, в каком порядке представители древней цивилизации записывали даты, вам, как главному специалисту по григорианскому календарю, поручили провести исследование — установить, каким датам в XXI веке могла соответствовать надпись, в предположении, что одно из чисел соответствует дню в месяце (дни в каждом месяце нумеровались с единицы), еще одно из чисел — номеру месяца (месяцы также нумеровались с единицы), и еще одно число — последним двум цифрам года в XXI веке григорианского календаря.

По заданной надписи на диске выясните, каким датам в XXI веке она могла соответствовать.

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

После долгих прений жюри утвердило регламент проведения соревнований. Соревнования длятся \(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\) страниц.

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