PROGRAMING PROBLEMS

Цэцэгчдийн дунд нэгэн сонирхолтой тэмцээн зохиожээ. Тэмцээн яг m өдөр үргэлжилнэ. Бүх оролцогчдод яг ижил дараалал бүхий n төрлийн цэцэг өгнө. Тэмцээн эхлэхэд эхний өдрийн 5:00 цагт оролцогч бүрийн i-р цэцэгний өндөр нь ai-тэй тэнцүү байна. Шөнө дунд болгон i-р цэцэг bi-ээр өндөр нь нэмэгдэж ургадаг. Өдөр бүрийн өглөө яг 6:00 цагт оролцогч бүр цэцэгнүүдээ нэг удаа тайрч болно. Тайрах үйлдлийг дараах байдлаар гүйцэтгэнэ: Оролцогч тайрахыг хүсэж буй цэцэгнүүдийн муж буюу мужийн зүүн хил i ба баруун хил j (1 ≤ i ≤ j ≤ n) дугаарыг сонгож, дараа нь l (0 ≤ l ≤ 2*109 ) тайрах өндрийг сонгож, i-ээс j хүртэл цэцэгнүүдийг өндөр нь l-ээс их бол l өндөртэй болгож тайрна. Тэмцээний дүнг m-р өдрийн үд дунд гаргана. Тэмцээний ялагч бол хамгийн цөөн тооны тайралт хийсний дараа бүх n цэцэг h өндөртэй болсон байх оролцогчид юм. 

Даалгавар: 

Ялагч болохын тулд хамгийн багадаа хэдэн удаа тайралт хийх ёстойг олоорой. 

Оролт: Оролтын эхний мөрөнд n, m, h гурван бүхэл тоо өгөгдөнө. Энд n (1 ≤ n ≤ 105 ) нь өгөгдсөн цэцэгний тоо, m (1 ≤ m ≤ 109 ) нь тэмцээний үргэлжлэх хугацаа, h (0 ≤ h ≤ 109 ) нь цэцэгнүүдийн шаардлагатай өндөр. Дараагийн n мөр тус бүр нь i-р цэцгийг тодорхойлох ai ба bi (0 ≤ ai, bi ≤ 109 ) хоёр бүхэл тоог агуулна. Энд ai нь i-р цэцэгний тэмцээний эхэнд байх өндөр, bi нь i-р цэцэгний нэг шөнийн дотор хэр их ургахыг тус тус илэрхийлнэ. 

Гаралт: Гаралтад тэмцээний төгсгөлд бүх цэцэг h өндөртэй байхын тулд шаардлагатай тайралтын хамгийн бага тоог хэвлээрэй. Хэрэв боломжгүй бол −1 тоог хэвлэнэ үү. Жишээ:

Оролт:

1 1 3 

2 1

Гаралт:

-1

Оролт:

2 2 3 

20 1 

10 1

Гаралт:

1