7200번 - Telecorp 스페셜 저지다국어

문제

NB! Lisaülesanne neile, kellel kõik teised juba lahendatud!

Rahvusvahelise teleportereid valmistava suurfirma Telecorp tehase ja labori vahel sõidab robootiline transporter. Tehas ja labor asuvad sirgel teel üksteisest L km kaugusel, tehas punktis 0 ja labor punktis L. Transporter alustab liikumist tehasest labori suunas kiirusega 1 km minutis.

Tee peal on N teleporterit, mis on seatud teleportima punktist A_i punkti B_i, kusjuures A_i < B_i ja teleporterid on ühesuunalised. Hetkel ei ole teleporterid võimelised transporterit teleportima, aga Telecorp kavatseb osadele teleporteritele paigaldada moodulid, mis teevad võimalikuks transporterit teleportida. Telecorp suudab toota M eri tüüpi mooduleid, kõiki piiramatus koguses. Teleporteril, millele on paigaldatud moodul j, kulub transporteri teleportimiseks C_j minutit. Lisaks on neil moodulitel üks eripära: osa teleportimisele kuluvast energiast saab taaskasutada transporteri kiirendamiseks. Kui transporter läbib mooduliga j varustatud teleporteri, hakkab transporter pärast seda liikuma V_j korda kiiremini. See laieneb kogu edasisele liikumisele, ka järgmised teleportimised on V_j korda kiiremad.

Telecorp soovib teada, kui kiirelt on võimalik moodulite optimaalse paigaldamise korral transporteril tehasest laborisse liikuda.

입력

Tekstifaili esimesel real on kolm täisarvu: teleporterite arv N (1 ≤ N ≤ 10⁵), moodulite tüüpide arv M (1 ≤ M ≤ 10⁵) ning tehase ja labori vaheline kaugus L (1 ≤ L ≤ 10⁹). Järgmisel N real on igaühel kaks täisarvu A_i ja B_i (0 ≤ A_i < B_i ≤ L), mis näitavad, et teleporter i telepordib punktist A_i punkti B_i. Viimasel M real on igaühel kaks reaalarvu C_j ja V_j (1 ≤ C≤ ≤ 10⁴, 1 ≤ V_j ≤ 10⁶), mis näitavad, et mooduli j abil telepordib teleporter algolekus tansporterit C_j minutiga ja kiirendab V_j korda.

출력

Tekstifaili televal.txt ainsale reale väljastada üks reaalarv, mis näitab, mitme minutiga suudab transporter liikuda tehasest laborisse optimaalse moodulite paigaldamise korral. Väljastatud vastus ei tohi täpsest väärtusest erineda rohkem kui 10⁻³ võrra.

제한

힌트