Задача №113676. Икебана
В Берляндии наступила эпоха просвещения. Уставшие от длительного средневековья, постоянных войн, драконов, прекрасных дам, рыцарей, спасающих прекрасных дам от драконов, и прочего героизма жители Берляндии обратились к прекрасному — к икебане. На этот год назначено проведение грандиозного соревнования среди любителей икебаны, однако в связи с недавно закончившимся средневековьем жюри испытывает массу проблем. В частности, в Берляндии из растений, пригодных для составления икебаны, остался только волшебный бамбук.
После долгих прений жюри утвердило регламент проведения соревнований. Соревнования длятся \(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\).
Теперь жюри интересно, какое минимальное число раз победителю придется стричь бамбук.
В первой строке входного файла находится три целых числа: \(n \ (1 \le n \le 10^5\) ) — количество ростков бамбука на грядке, \(m \ (1 \le m \le 10^9\) ) — длительность соревнований, и \(h \ (0 \le h \le 10^9\) ) — высота всех ростков, необходимая для победы.
В следующих \(n\) строках находится по два целых числа \(a_i\) и \(b_i \ (0 \le a_i , \ b_i \le 10^9\) ) — описание \(i\)-го ростка: его высота в момент начала соревнований и на сколько он вырастает за ночь, соответственно.
В выходной файл выведите одно число — минимальное число стрижек бамбука, необходимое, чтобы весь бамбук в конце соревнования имел высоту \(h\), либо число \(−1\), если это невозможно.
В первом примере подведение итогов происходит в тот же день, что и начало соревнований. Для победы необходимо иметь росток бамбука высотой 3, но бамбук растет в полночь, и между 5 утра и полуднем высота бамбука не изменится и останется равной 2. При этом стрижка бамбука позволяет лишь уменьшить его высоту, поэтому достичь цели невозможно.
Во втором примере можно, например, подстричь все ростки бамбука в первый день до высоты 2, ночью все ростки бамбука вырастут на 1 и будут иметь искомую высоту к полудню второго дня.
1 1 3 2 1
-1
2 2 3 20 1 10 1
1