IOI елі өзінің көлік желісін жан-жақты дамыту туралы шешім қабылдады. IOI елі $xy$ координаталық жазықтығы ретінде бейнеленеді, онда $N$ қала орналасқан. $i$-ші қала ($1 \le i \le N$) $(X_i, Y_i)$ нүктесі ретінде көрсетіледі. Көлік желісін дамыту келесі тәртіппен жүзеге асырылады:

• $N$ қаланың кейбірінде халықаралық әуежайлар салу. Кемінде бір халықаралық әуежай салынуы тиіс. Салынған әрбір халықаралық әуежай белгілі бір тұрақты шығынды талап етеді.
• Қалаларды байланыстыратын бірнеше жол салу. Жол дегеніміз — қалаларды білдіретін екі нүктені тікелей қосатын, $x$ осіне немесе $y$ осіне параллель кесінді. Салынған әрбір жол оның ұзындығына тең шығынды талап етеді.

Бұл ретте келесі шарттар орындалуы тиіс:

• IOI елінде топырақ жағдайының нашарлығынан немесе басқа себептермен жол салуға болмайтын $M$ аймақ бар. Әрбір аймақ тіктөртбұрыш ретінде беріледі; $j$-ші тіктөртбұрыштың ($1 \le j \le M$) сол жақ төменгі бұрышы $(P_j, Q_j)$ нүктесінде, ал оң жақ жоғарғы бұрышы $(R_j, S_j)$ нүктесінде орналасқан (мұндағы $P_j < R_j$ және $Q_j < S_j$). Ешбір жол $M$ аймақтың ешқайсысымен қиылыспауы тиіс. Аймақтар өз шекараларын қамтиды, сондықтан ешбір жол аймақты білдіретін тіктөртбұрыштың шекарасымен де қиылыспауы тиіс.
• $N$ қаланың кез келгенінен басқа қалаларға жолдар арқылы бірнеше рет жүріп өтіп, халықаралық әуежайы бар қалаға жету мүмкін болуы тиіс.

Бұл жобаға $C$ құрылыс компаниясы үміткер болып отыр. $k$-шы құрылыс компаниясы ($1 \le k \le C$) бір халықаралық әуежай салу үшін $B_k$ шығын жұмсайды және ең көп дегенде $H_k$ халықаралық әуежай сала алады (жол салу құны құрылыс компаниясына байланысты емес, және жолдардың санына немесе ұзындығына ешқандай шектеу жоқ). Әрбір құрылыс компаниясы үшін жоғарыдағы шарттар орындалатындай етіп көлік желісін дамытудың ең аз жалпы құнын табу қажет.

Салынуы мүмкін халықаралық әуежайлар саны аз болғандықтан, шарттарды қанағаттандыра отырып көлік желісін дамыта алмайтын құрылыс компаниялары болуы мүмкін. Мұндай жағдайларда жалпы құнның орнына шарттарды орындау мүмкін емес екенін хабарлаңыз.

Тапсырма

IOI еліндегі қалалар санын білдіретін $N$ бүтін саны мен олардың координаталары, жол салуға болмайтын аймақтар санын білдіретін $M$ бүтін саны мен олардың координаталары, сондай-ақ үміткер құрылыс компанияларының санын білдіретін $C$ бүтін саны мен олар туралы ақпарат берілген. Есептің шартында сипатталған талаптарды орындай отырып, көлік желісін дамыту үшін әрбір құрылыс компаниясына қажетті ең аз жалпы құнды есептейтін программа жазыңыз.

Кіріс деректер

Стандартты енгізуден келесі деректерді оқыңыз:

• Бірінші жолда бос орындармен бөлінген үш бүтін сан $N, M, C$ берілген — олар сәйкесінше IOI еліндегі қалалар санын, жол салуға болмайтын аймақтар санын және үміткер құрылыс компанияларының санын білдіреді.
• Келесі $N$ жолдың $i$-ші жолында ($1 \le i \le N$) бос орындармен бөлінген екі бүтін сан $X_i, Y_i$ берілген — олар $i$-ші қаланың $(X_i, Y_i)$ координаталарын білдіреді.
• Келесі $M$ жолдың $j$-ші жолында ($1 \le j \le M$) бос орындармен бөлінген төрт бүтін сан $P_j, Q_j, R_j, S_j$ берілген — олар жол салуға болмайтын $j$-ші тіктөртбұрыштың сол жақ төменгі $(P_j, Q_j)$ нүктесі мен оң жақ жоғарғы $(R_j, S_j)$ нүктесінің координаталарын білдіреді.
• Келесі $C$ жолдың $k$-шы жолында ($1 \le k \le C$) бос орындармен бөлінген екі бүтін сан $B_k, H_k$ берілген — олар $k$-шы үміткер құрылыс компаниясының бір халықаралық әуежайға $B_k$ шығын жұмсайтынын және ең көп дегенде $H_k$ халықаралық әуежай сала алатынын білдіреді.

Шығыс деректер

Стандартты шығаруға $C$ жол шығарыңыз. $k$-шы жолда ($1 \le k \le C$) $k$-шы үміткер құрылыс компаниясының осы жобаны жүзеге асыруына қажетті ең аз жалпы құнды білдіретін бір бүтін сан болуы тиіс. Алайда, егер $k$-шы үміткер құрылыс компаниясы шарттарды қанағаттандыра отырып жобаны орындай алмаса, оның орнына $-1$ шығарыңыз.

Шектеулер

Барлық кіріс деректер келесі шарттарды қанағаттандырады:

• $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$).
• Ешбір екі қала бірдей координаталарда орналаспаған.
• $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$).
• Ешбір аймақтың ішінде немесе шекарасында қала жоқ.
• $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$).

Ішкі тапсырмалар

Ішкі тапсырма 1 [10 ұпай]

Келесі шарттарды қанағаттандырады:

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

Ішкі тапсырма 2 [30 ұпай]

Келесі шартты қанағаттандырады:

• $C \le 100$.

Ішкі тапсырма 3 [30 ұпай]

Келесі шартты қанағаттандырады:

• $M \le 100$.

Ішкі тапсырма 4 [30 ұпай]

Қосымша шектеулер жоқ.

Мысалдар

Кіріс 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

Шығыс 1

28
38
-1

Ескертпе

Мысалдағы кіріс деректерді келесідей бейнелеуге болады. Қалың сызықтармен сызылған тіктөртбұрыштар жол салуға болмайтын аймақтарды көрсетеді.

2-ші қала мен 4-ші қаланы, сондай-ақ 3-ші қала мен 4-ші қаланы қосатын жолдарды салу мүмкін болғанымен, 1-ші қала мен 2-ші қаланың арасында жол салу мүмкін емес, себебі ол жол салуға болмайтын аймақпен қиылысады. Дәл сол сияқты, 1-ші қала мен 3-ші қаланың арасында да жол салу мүмкін емес (жолдар тіктөртбұрыштардың шекараларымен де қиылыспауы тиіс екеніне назар аударыңыз).

Бірінші құрылыс компаниясы әрқайсысының құны 7 болатын ең көп дегенде 4 халықаралық әуежай сала алады. Бұл жағдайда ешқандай жол салмай, барлық қалаларда халықаралық әуежай салу ең тиімді шешім болады, және жалпы құны $7 \times 4 = 28$ құрайды.

Екінші құрылыс компаниясы әрқайсысының құны 10 болатын ең көп дегенде 3 халықаралық әуежай сала алады. Бұл жағдайда, мысалы, 2-ші қала мен 4-ші қаланы, сондай-ақ 3-ші қала мен 4-ші қаланы қосатын ұзындығы 9 болатын жолдарды салып, 1-ші қала мен 2-ші қалада халықаралық әуежайлар салған жөн. Жалпы құны $10 \times 2 + 9 + 9 = 38$ құрайды.

Үшінші құрылыс компаниясы әрқайсысының құны 1 болатын ең көп дегенде 1 халықаралық әуежай сала алады, бірақ 1-ші қаладан басқа ешбір қалаға жол салу мүмкін болмағандықтан, есептің шарттарын қанағаттандыру үшін кемінде 2 халықаралық әуежай салынуы керек. Демек, бұл компания жобаны орындай алмайтыны анық, сондықтан біз $-1$ шығарамыз.