Landið IOI hefur ákveðið að ráðast í heildstæða uppbyggingu á samgöngukerfi sínu. IOI er táknað sem $xy$-hnitaslétta þar sem eru $N$ bæir. $i$-ti bærinn ($1 \le i \le N$) er táknaður sem punktur $(X_i, Y_i)$. Uppbygging samgöngukerfisins fer fram samkvæmt eftirfarandi verklagi:

• Byggja alþjóðaflugvelli í nokkrum af bæjunum $N$. Byggja verður að minnsta kosti einn alþjóðaflugvöll. Hver alþjóðaflugvöllur sem byggður er hefur fastan kostnað í för með sér.
• Byggja nokkra vegi sem tengja saman bæi. Vegur er strik samsíða $x$-ásnum eða $y$-ásnum sem tengir beint saman tvo punkta sem tákna bæi. Hver vegur sem byggður er hefur kostnað í för með sér sem jafngildir lengd hans.

Á sama tíma verða eftirfarandi skilyrði að vera uppfyllt:

• Það eru $M$ svæði í IOI þar sem ekki er hægt að byggja vegi vegna slæmra jarðvegsskilyrða eða annarra ástæðna. Hvert svæði er táknað sem rétthyrningur; $j$-ti rétthyrningurinn ($1 \le j \le M$) hefur neðra vinstra hornið í $(P_j, Q_j)$ og efra hægra hornið í $(R_j, S_j)$ (þar sem $P_j < R_j$ og $Q_j < S_j$). Enginn vegur má hafa nokkurn skurðpunkt við neitt af svæðunum $M$. Svæðin innihalda jaðra sína, og enginn vegur má hafa nokkurn skurðpunkt við jaðar nokkurs rétthyrnings sem táknar svæði.
• Það verður að vera hægt að komast í bæ með alþjóðaflugvelli frá hvaða bæ sem er af bæjunum $N$ með því að ferðast endurtekið eftir vegum til annarra bæja.

Það eru $C$ byggingarfyrirtæki sem koma til greina fyrir þetta verkefni. $k$-ta byggingarfyrirtækið ($1 \le k \le C$) ber kostnað upp á $B_k$ við að byggja einn alþjóðaflugvöll og getur í mesta lagi byggt $H_k$ alþjóðaflugvelli (kostnaðurinn við að byggja vegi er óháður byggingarfyrirtækinu og engar takmarkanir eru á fjölda eða lengd vega). Fyrir hvert byggingarfyrirtæki viljum við finna lágmarks heildarkostnað við að byggja upp samgöngukerfið þannig að ofangreind skilyrði séu uppfyllt.

Þar sem fjöldi alþjóðaflugvalla sem hægt er að byggja er lítill gætu verið til byggingarfyrirtæki sem geta ekki byggt upp samgöngukerfið þannig að skilyrðin séu uppfyllt. Í slíkum tilvikum skal tilkynna að ekki sé hægt að uppfylla skilyrðin í stað heildarkostnaðarins.

Verkefni

Gefið heiltöluna $N$ sem táknar fjölda bæja í IOI og hnit þeirra, heiltöluna $M$ sem táknar fjölda svæða þar sem ekki er hægt að byggja vegi og hnit þeirra, og heiltöluna $C$ sem táknar fjölda byggingarfyrirtækja sem koma til greina og upplýsingar um þau, skrifið forrit sem reiknar lágmarks heildarkostnað fyrir hvert byggingarfyrirtæki við að byggja upp samgöngukerfið þannig að skilyrðin í verkefnislýsingunni séu uppfyllt.

Inntak

Lesið eftirfarandi inntak úr staðalinntaki:

• Fyrsta línan inniheldur þrjár heiltölur $N, M, C$, aðskildar með bilum, sem tákna fjölda bæja í IOI, fjölda svæða þar sem ekki er hægt að byggja vegi og fjölda byggingarfyrirtækja sem koma til greina, í þessari röð.
• $i$-ta línan af næstu $N$ línum ($1 \le i \le N$) inniheldur tvær heiltölur $X_i, Y_i$, aðskildar með bilum, sem tákna hnitin $(X_i, Y_i)$ fyrir $i$-ta bæinn.
• $j$-ta línan af næstu $M$ línum ($1 \le j \le M$) inniheldur fjórar heiltölur $P_j, Q_j, R_j, S_j$, aðskildar með bilum, sem tákna hnit neðri vinstri punktsins $(P_j, Q_j)$ og efri hægri punktsins $(R_j, S_j)$ á $j$-ta rétthyrningnum þar sem ekki er hægt að byggja vegi.
• $k$-ta línan af næstu $C$ línum ($1 \le k \le C$) inniheldur tvær heiltölur $B_k, H_k$, aðskildar með bilum, sem tákna að $k$-ta byggingarfyrirtækið sem kemur til greina beri kostnað upp á $B_k$ fyrir hvern alþjóðaflugvöll og geti í mesta lagi byggt $H_k$ alþjóðaflugvelli.

Úttak

Skrifið $C$ línur í staðalúttak. $k$-ta línan ($1 \le k \le C$) á að innihalda eina heiltölu sem táknar lágmarks heildarkostnað fyrir $k$-ta byggingarfyrirtækið til að framkvæma þetta verkefni. Hins vegar, ef $k$-ta byggingarfyrirtækið getur ekki framkvæmt verkefnið þannig að skilyrðin séu uppfyllt, skrifið þá $-1$ í staðinn.

Takmarkanir

Öll inntaksgögn uppfylla eftirfarandi skilyrði:

• $1 \le N \le 200\,000$.
• $1 \le M \le 200\,000$.
• $1 \le C \le 500\,000$.
• $0 \le X_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
• $0 \le Y_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
• Engir tveir bæir hafa sömu hnit.
• $0 \le P_j < R_j \le 1\,000\,000\,000$ ($1 \le j \le M$).
• $0 \le Q_j < S_j \le 1\,000\,000\,000$ ($1 \le j \le M$).
• Ekkert svæði inniheldur bæ innan í sér eða á jaðri sínum.
• $1 \le B_k \le 1\,000\,000\,000$ ($1 \le k \le C$).
• $1 \le H_k \le N$ ($1 \le k \le C$).

Undirverkefni

Undirverkefni 1 [10 stig]

Uppfyllir eftirfarandi skilyrði:

• $M \le 100$.
• $C \le 100$.

Undirverkefni 2 [30 stig]

Uppfyllir eftirfarandi skilyrði:

• $C \le 100$.

Undirverkefni 3 [30 stig]

Uppfyllir eftirfarandi skilyrði:

• $M \le 100$.

Undirverkefni 4 [30 stig]

Engar frekari takmarkanir.

Dæmi

Inntak 1

4 2 3
1 1
10 1
1 10
10 10
4 0 8 9
1 4 9 8
7 4
10 3
1 1

Úttak 1

28
38
-1

Athugasemd

Sýnidæmið má skýra með eftirfarandi mynd. Rétthyrningarnir með þykku línunum sýna svæðin þar sem ekki er hægt að byggja vegi.

Þótt hægt sé að byggja vegi sem tengja Bæ 2 og Bæ 4, og Bæ 3 og Bæ 4, er ekki hægt að byggja veg milli Bæjar 1 og Bæjar 2 vegna þess að hann myndi skerast við svæði þar sem ekki er hægt að byggja vegi. Á sama hátt er ekki hægt að byggja veg milli Bæjar 1 og Bæjar 3 (athugið að vegir mega ekki hafa neinn skurðpunkt við jaðra rétthyrninganna).

Fyrsta byggingarfyrirtækið getur í mesta lagi byggt 4 alþjóðaflugvelli með kostnaði 7 hver. Í þessu tilviki er best að byggja alþjóðaflugvelli í öllum bæjum án þess að byggja neina vegi, og heildarkostnaðurinn er $7 \times 4 = 28$.

Annað byggingarfyrirtækið getur í mesta lagi byggt 3 alþjóðaflugvelli með kostnaði 10 hver. Í þessu tilviki er best að byggja til dæmis vegi af lengd 9 sem tengja Bæ 2 og Bæ 4, og Bæ 3 og Bæ 4, og byggja alþjóðaflugvelli í Bæ 1 og Bæ 2. Heildarkostnaðurinn er $10 \times 2 + 9 + 9 = 38$.

Þriðja byggingarfyrirtækið getur í mesta lagi byggt 1 alþjóðaflugvöll með kostnaði 1 hver, en þar sem ekki er hægt að leggja veg frá Bæ 1 til neins annars bæjar verður að byggja að minnsta kosti 2 alþjóðaflugvelli til að uppfylla skilyrðin í verkefnislýsingunni. Því er ljóst að þetta fyrirtæki getur ekki framkvæmt verkefnið, svo við skrifum út $-1$.