Задачи отборочных командных соревнований школьников 2011

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

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

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

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

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

Во входном файле в формате `"aa"//"bb"//"cc"` записаны числа с диска.

В выходной файл в произвольном порядке выведите все корректные даты `"dd"//"mm"//"yy"` в XXI веке, где `"dd"` соответствует номеру дня, `"mm"` -- номеру месяца, `"yy"` — номеру года, причем числа, соответствующие `"dd"`, `"mm"` и `"yy"` являются перестановками чисел с диска.

В случае, если никакая перестановка исходных чисел не является корректной датой XXI века, выведите "No such date".

29/02/04

29/02/04
29/04/02
02/04/29
04/02/29

01/01/01

01/01/01

99/99/99

No such date

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

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

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

В первой строке входного файла находится три целых числа: `n` (`1\ ≤\ n\ ≤\ 10^5`) — количество ростков бамбука на грядке, `m` (`1\ ≤\ m\ ≤\ 10^9`) — длительность соревнований, и `h` (`0\ ≤\ h\ ≤\ 10^9`) — высота всех ростков, необходимая для победы.

В следующих `n` строках находится по два целых числа `a_i` и `b_i` `(0\ ≤\ a_i,\ b_i\ ≤\ 10^9)` — описание `i`-го ростка: его высота в момент начала соревнований и на сколько он вырастает за ночь, сооветственно.

В выходной файл выведите одно число — минимальное число стрижек бамбука, необходимое, чтобы весь бамбук в конце соревнования имел высоту `h`, либо число `-1`, если это невозможно.

1 1 3
2 1

-1

2 2 3
20 1
10 1