04/04/2025 23:18:48

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

1687. Икебана

Ограничения: время – 2s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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

После долгих прений жюри утвердило регламент проведения соревнований. Соревнования длятся

$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 1 3
2 1

Пример вывода 1

-1

Пример ввода 2

2 2 3
20 1
10 1

Пример вывода 2

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

Во втором примере можно, например, подстричь все ростки бамбука в первый день до высоты 2, ночью все ростки бамбука вырастут на 1 и будут иметь искомую высоту к полудню второго дня.

Источник: XIX Командный чемпионат школьников Санкт-Петербурга по программированию, 2011