0219. Икебана

Input file name:	garden.in
Output file name:	garden.out
Time limit:	2 s
Memory limit:	256 megabytes

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

После долгих прений жюри утвердило регламент проведения соревнований. Соревнования длятся 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 строках находится по два целых числа a_i и b_i (0 ≤ a_i, b_i ≤ 10⁹) – описание i-го ростка: его высота в момент начала соревнований и на сколько он вырастает за ночь, сооветственно.

Формат выходного файла

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

Пример:

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

garden.in	garden.out
1 1 3 2 1	-1
2 2 3 20 1 10 1	1

Source: Командное школьное первенство Республики Карелия по программированию, 30 октября 2011.

Discuss       Submit a solution



Printable version