Framkvæmdastjórinn K elskar spádóma og framkvæmir oft ýmsar spár. Í dag ákvað hann að spá fyrir um gengi japanska liðsins á IOI í ár með því að nota spil með 'I' á framhliðinni og 'O' á bakhliðinni.

Aðferðin við spádóminn er sem hér segir:

1. Fyrst skal ákveða jákvæðar heiltölur $A, B, C, D, E$.
2. Raðið $A + B + C + D + E$ spilum í eina röð. Á þessum tímapunkti skal raða $A$ spilum á réttunni (með framhliðina upp), þar á eftir $B$ spilum á hvolfi (með bakhliðina upp), þar á eftir $C$ spilum á réttunni, þar á eftir $D$ spilum á hvolfi og að lokum $E$ spilum á réttunni. Að raða þeim á þennan hátt gefur runu af $A$ 'I'-um, $B$ 'O'-um, $C$ 'I'-um, $D$ 'O'-um og $E$ 'I'-um frá vinstri til hægri.
3. Veljið eina eða fleiri aðgerðir úr $N$ fyrirfram ákveðnum tegundum og framkvæmið þær í hvaða röð sem er. Þú mátt framkvæma sömu tegund aðgerðar tvisvar eða oftar. $i$-ta tegund aðgerðar ($1 \le i \le N$) er að "snúa við öllum spilum frá $L_i$-ta spilinu til $R_i$-ta spilsins frá vinstri". Að snúa við einu spili tekur 1 sekúndu. Því tekur $R_i - L_i + 1$ sekúndur að framkvæma $i$-tu aðgerðina.
4. Eftir að aðgerðunum er lokið heppnast spádómurinn ef öll spilin eru á réttunni.

Til að forðast að snúa spilum oftar en þörf krefur ákvað framkvæmdastjórinn K að kanna hvort hægt væri að láta spádóminn heppnast áður en spilin eru raunverulega notuð. Ennfremur, ef hægt er að láta spádóminn heppnast, ákvað hann að finna lágmarkstímann sem þarf til þess.

Verkefni

Gefnar eru upplýsingar um uppröðun spilanna og fyrirfram ákveðnu aðgerðirnar. Skrifið forrit til að ákvarða hvort hægt sé að láta spádóminn heppnast, og ef svo er, finna lágmarkstímann sem þarf til að láta hann heppnast.

Inntak

Lesið eftirfarandi gögn úr staðalinntaki:

• Fyrsta línan inniheldur heiltölurnar $A, B, C, D, E$ aðskildar með bilum. Þetta táknar að í upphafi spádómsins eru $A$ spil á réttunni, þar á eftir $B$ spil á hvolfi, þar á eftir $C$ spil á réttunni, þar á eftir $D$ spil á hvolfi og $E$ spil á réttunni.
• Önnur línan inniheldur heiltölu $N$, sem táknar að það eru $N$ tegundir af fyrirfram ákveðnum aðgerðum.
• $i$-ta línan af næstu $N$ línum ($1 \le i \le N$) inniheldur heiltölurnar $L_i, R_i$ aðskildar með bilum. Þetta táknar að $i$-ta aðgerðin er að "snúa við öllum spilum frá $L_i$-ta spilinu til $R_i$-ta spilsins frá vinstri".

Úttak

Ef hægt er að láta spádóminn heppnast skal skrifa út lágmarkstímann sem þarf til að láta hann heppnast sem heiltölu á einni línu. Annars skal skrifa út -1.

Skorður

Öll inntaksgögn uppfylla eftirfarandi skilyrði:

• $1 \le A \le 100\,000$.
• $1 \le B \le 100\,000$.
• $1 \le C \le 100\,000$.
• $1 \le D \le 100\,000$.
• $1 \le E \le 100\,000$.
• $1 \le N \le 100\,000$.
• $1 \le L_i \le R_i \le A + B + C + D + E$ ($1 \le i \le N$).

Undirverkefni

Undirverkefni 1 [15 stig]

• $N \le 10$ er uppfyllt.

Undirverkefni 2 [50 stig]

• Eftirfarandi skilyrði eru uppfyllt:
  • $1 \le A \le 50$.
  • $1 \le B \le 50$.
  • $1 \le C \le 50$.
  • $1 \le D \le 50$.
  • $1 \le E \le 50$.

Undirverkefni 3 [35 stig]

• Engar frekari skorður eru til staðar.

Dæmi

Inntak 1

1 2 3 4 5
3
2 3
2 6
4 10

Úttak 1

12

Skýring 1

Í upphafi er spilunum raðað sem IOOIIIOOOOIIIII. Framkvæmd 2. aðgerðarinnar gefur IIIOOOOOOOIIIII. Þessi aðgerð tekur 5 sekúndur. Í kjölfarið gefur framkvæmd 3. aðgerðarinnar IIIIIIIIIIIIIII og spádómurinn heppnast. Þessi aðgerð tekur 7 sekúndur. Hægt er að láta spádóminn heppnast á 12 sekúndum. Þar sem þetta er lágmarksgildið skal skrifa út 12.

Inntak 2

1 1 1 1 1
1
1 1

Úttak 2

-1

Skýring 2

Í þessu inntaksdæmi er ekki hægt að láta spádóminn heppnast, svo skrifa skal út -1.