Problem N
Skrift

Bjarki að skrifa

Bjarki gleymdi samt öllu strokleðrinu sínu heima þannig nú er hann í klandri. Hann biður því vin sinn Unnar um að fara í A4 að kaupa strokleður fyrir sig. Unnar er svo góðhjartaður strákur að hann samþykkir það og fer í A4. Á leiðinni í A4 fattar Unnar að hann veit ekki hversu mikið Bjarki mun stroka út og er alveg í losti. Hann ákveður því að fara fyrst til Diddu spákonu og spyrja hana.

Didda spákona er dularfull kona. Hún sagði Unnari að það væri hægt að lýsa skrift Bjarka í $Q$ aðgerðum þar sem hver aðgerð samanstendur af tveimur heiltölum $x_ i,y_ i$. Ef $x_ i = 1$ þá þýðir það að Bjarki skrifi $y_ i$ stafi, en ef $x_ i = 2$ þá þýðir það að Bjarki strokar út síðustu $y_ i$ stafina. Glaður stekkur Unnar út og aftur í A4 en nú hugsar Unnar: af öllum strengjum sem Bjarki gæti verið að skrifa sem er hægt að lýsa með þessum $Q$ aðgerðum hvað er mesta magn af strokleðri sem Bjarki gæti þurft?

Nú hringir Unnar í þig með öllum þessum upplýsingum og spyr þig um hjálp. Hvað á Unnar að kaupa mörg milligrömm af strokleðri?

Inntak

Fyrsta línan í inntakinu inniheldur þrjár heiltölur $1 \le n \le 10^9, 1 \le m,q \le 10^5$. Næstu $m$ línur innihalda hver tvær heiltölur $1 \le a_ i \le n, 1 \le b_ i \le 10^4$. Næstu $q$ línur innihalda hver tvær heiltölur $1 \le x_ i \le 2, 1 \le y_ i \le n$.

Gefið er að summan af öllum $a_ i$ er alltaf $n$. Bjarki mun aldrei skrifa fleiri stafi heldur en eru í orðinu. Einnig mun Bjarki aldrei stroka út fleiri stafi en hafa verið skrifaðir.

Úttak

Skrifið út eina tölu, hversu mikið strokleður í milligrömmum þarf Unnar að kaupa til að vera viss um að hann sé með nóg. Svarið mun aldrei vera meira en $10^{18}$.

Stigagjöf

4 2 4
2 4
2 2
1 1
1 2
2 2
1 3

8

3 2 3
1 3
2 2
1 3
2 3
1 3

7