Програмчлалын олимпиадын бодлогын архив

Шахеразадагийн хэлснээр бол холын холд цөлийн дунд нуур байдаг. Анх уг нууранд F ширхэг загас байсан. Дэлхий дээр байдаг сувднуудын K ширхэг ялгаатай төрлийг сонгон авч F ширхэг загас бүрт яг нэг нэг сувд залгиулжээ. K нь F – ээс бага байж болох тул хоёр болон түүнээс олон загас нэг төрлийн сувд залгисан байж болно.
Хэсэг хугацааны дараа зарим загас нь бусад загаснуудаасаа иджээ. Хэрэв эхний загасны урт хоёр дахь загасны уртаас дор хаяж хоёр дахин их бол эхний загас хоёр дахь загасаа идэж чадна (зөвхөн L_A >= 2 * L_B үед л загас A нь загас B – гээ идэж чадна). Загас хэзээ иддэг тухай дүрэм байхгүй. Зарим загас хэд хэдэн жижиг загасыг дараалан идэж болох бол зарим загас нь идэж чадах боловч ямар ч загасыг идэхгүй байж болно. Загас өөрөөсөө жижиг загасыг идэх үед тууний урт өөрчлөгдөхгүй ба жижиг загасны ходоодонд байсан сувд бүтнээрээ том загасны ходоодонд үлдэнэ.
Шахеразада танд хэрэв нуурыг олж чадах юм бол дотроос нь ганц загас барьж болох ба түүний ходоодонд байгаа бүх сувдыг өөртөө аваарай гэж хэлсэн. Та азаа үзэхээр шийдсан ба урт аян замд гарахынхаа өмнө ганц загас барьснаар хэдэн ялгаатай сувдны хослолыг олж чадахаа мэдэхийг хүсч байгаа.
ДААЛГАВАР
Загас бүрийн урт болон анх ямар төрлийн сувд залгисан нь өгөгдсөн бол ямар нэг загас барихад ходоодонд нь байх сувднуудын ялгаатай хослолуудын тоог өгөгдсөн M бүхэл тоонд хуваасны үлдэгдлийг олох програм бич. Хослол нь K төрөл бүрээс хэдэн сувд байгаагаараа тодорхойлогдоно. Сувднуудын дарааллыг тооцохгүй ба нэг төрлийн хоёр сувдыг ялгаагүй гэж үзнэ.
ХЯЗГААРЛАЛТУУД
1 <= F <= 500,000 Нууранд анх байсан загасны тоо.
1 <= K <= F Сувдны ялгаатай төрлүүдийн тоо.
2 <=M <= 30,000
1 <= L_X <= 1,000,000,000 X загасны урт.

Input

Таны програм стандарт оролтоос дараах өгөгдлийг унших ёстой:
• Нэгдүгээр мөрөнд нууранд анх байсан загасны тоо болох F бүхэл тоо байрлана.
• Хоёрдугаар мөрөнд сувднуудын төрлийн тоо болох K бүхэл тоо байрлана.
Сувдны төрлийг 1-ээс багагүй, K – гаас ихгүй бүхэл тоогоор илэрхийлнэ.
• Гуравдугаар мөрөнд M бүхэл тоо байрлана.
• Дараагийн F ширхэг мөр бүрт зайгаар тусгаарлагдсан хоёр бүхэл тоогоор нэг загасыг тодорхойлно: эхлээд загасны урт, дараа нь уг загасны анх залгисан сувдны төрөл байна.
ТАЙЛБАР: Бодлогыг шалгахад хэрэглэгдэж буй тест бүрийн хувьд сувдны K төрөл бүрээс дор хаяж нэг сувд байна.

Output

Таны програм стандарт гаралт руу сувднуудын боломжит бүх хувилбаруудын тоог M – д хуваасны үлдэгдэл болох 0-ээс багагүй, M-1 – гээс ихгүй нэг бүхэл тоог гаргах ёстой. Бодлогын бодолтонд M – ийн утга тооцооллыг хялбарчлахаас өөр үүрэггүй болохыг анхаарна уу.
ҮНЭЛГЭЭ
Нийт тестийн 70 хувьд нь K – гийн утга 7,000 – аас хэтрэхгүй.
Мөн нийт тестийн 25 хувьд нь K – гийн утга 20 – оос хэтрэхгүй.

Example

Input:
5
3
7
2 2
5 1
8 3
4 1
2 3


Output:
4

Энд 11 ширхэг боломжит хослолууд байгаа тул 7 – д хуваасны үлдэгдэл болох 4 – ийг гаргана.
Боломжит хослолууд нь: [1] [1,2] [1,2,3] [1,2,3,3] [1,3] [1,3,3] [2] [2,3] [2,3,3] [3] болон [3,3] юм.
(Хослол бүрийн хувьд бид түүнд агуулагдах сувднуудыг жагсаалаа. Жишээ нь [2,3,3] гэдэг нь 2-р төрлийн нэг сувд, 3-р төрлийн хоёр сувд агуулах хослол юм.)
Эдгээр хослолуудыг дараах байдлаар гарган авч болно:
• [1]: Өөр ямар нэг загасыг залгихаас нь өмнө хоёр дахь (эсвэл дөрөв дэх) загасыг барих.
• [1,2]: Хоёр дахь загас нэгдүгээр загасыг залгисны дараа ходоодондоо 1-р төрлийн сувд нэг(анх залгисан), 2-р төрлийн сувд нэгийг (нэгдүгээр загасны ходоодонд байсан) агуулна.
• [1,2,3]: Энэ хослолыг гарган авах нэг арга нь дөрөв дэх загас нэгдүгээр загасыг идээд дараа нь гуравдугаар загас дөрөв дэх загасыг идэх явдал юм. Ингэсний дараа та гуравдугаар загасыг баривал ходоодонд нь төрөл бүрээс нэг нэг сувд байх болно.
• [1,2,3,3]: Дөрөв дэх загас нэгдүгээр загасыг идэж, гурав дахь загас дөрөв дэх загасыг идэж, гурав дахь загас тав дахь загасыг идсэний дараа та гурав дахь загасыг барих.
• [1,3]: Гурав дахь загас дөрөв дэхийг идсэний дараа та түүнийг барих.
• [1,3,3]: Гурав дахь загас тав дахь загасыг идээд, гурав дахь загас дөрөв дэх загасыг идсэний дараа та түүнийг барих.
• [2]: Нэгдүгээр загасыг барих.
• [2,3]: Гурав дахь загас нэгдүгээр загасыг идсэний дараа та түүнийг барих.
• [2,3,3]: Гурав дахь загас нэгдүгээр загасыг идээд, гурав дахь загас тав дахь загасыг идсэний дараа та түүнийг барих.
• [3]: Гурав дахь загасыг барих.
• [3,3]: Гурав дахь загас тав дахь загасыг идсэний дараа та түүнийг барих.