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

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

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

1

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

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