В Берляндии наступила эпоха просвещения

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

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

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

В первой строке входного файла находится три целых числа: n (1<=n<=10⁵ ) — количество ростков бамбука на грядке, m (1<=m<=10⁹ ) — длительность соревнований, и h (0<=h<=10⁹ ) — высота всех ростков, необходимая для победы.

В следующих n строках находится по два целых числа ai и bi (0<=a_i; b_i<=10⁹ ) — описание i -го ростка: его высота в момент начала соревнований и на сколько он вырастает за ночь, соответственно.
Выходные данные

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

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

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


Примеры

Входные данные

1 1 3

2 1

Выходные данные

-1

Входные данные

2 2 3

20 1

10 1

Выходные данные

1

0