Direktør K elsker spådomskunst og utfører ofte ulike spådommer. I dag bestemte han seg for å spå prestasjonen til det japanske laget i årets IOI ved hjelp av kort med 'I' på forsiden og 'O' på baksiden.

Spådomsmetoden er som følger:

1. Bestem først positive heltall $A, B, C, D, E$.
2. Legg $A + B + C + D + E$ kort på én enkelt rad. Legg da $A$ kort med forsiden opp, etterfulgt av $B$ kort med forsiden ned, etterfulgt av $C$ kort med forsiden opp, etterfulgt av $D$ kort med forsiden ned, og til slutt $E$ kort med forsiden opp. Å legge dem på denne måten resulterer i en sekvens av $A$ 'I'-er, $B$ 'O'-er, $C$ 'I'-er, $D$ 'O'-er og $E$ 'I'-er fra venstre mot høyre.
3. Velg én eller flere operasjoner blant $N$ forhåndsbestemte typer og utfør dem i hvilken som helst rekkefølge. Du kan utføre samme type operasjon to eller flere ganger. Den $i$-te typen operasjon ($1 \le i \le N$) er å "snu alle kort fra det $L_i$-te kortet til det $R_i$-te kortet fra venstre". Å snu ett kort tar 1 sekund. Derfor tar det $R_i - L_i + 1$ sekunder å utføre den $i$-te operasjonen.
4. Etter at operasjonene er fullført, er spådommen vellykket hvis alle kortene ligger med forsiden opp.

For å unngå å snu kort mer enn nødvendig bestemte direktør K seg for å avgjøre om det er mulig å gjøre spådommen vellykket før han faktisk bruker kortene. Videre, hvis det er mulig å gjøre spådommen vellykket, bestemte han seg for å finne den minste tiden som kreves for å få det til.

Oppgave

Gitt informasjon om oppstillingen av kortene og de forhåndsbestemte operasjonene, skriv et program for å avgjøre om det er mulig å gjøre spådommen vellykket, og i så fall finne den minste tiden som kreves for å gjøre den vellykket.

Inndata

Les følgende data fra standard inndata:

• Den første linjen inneholder heltallene $A, B, C, D, E$ adskilt med mellomrom. Dette representerer at ved begynnelsen av spådommen ligger $A$ kort med forsiden opp, etterfulgt av $B$ kort med forsiden ned, etterfulgt av $C$ kort med forsiden opp, etterfulgt av $D$ kort med forsiden ned, og $E$ kort med forsiden opp.
• Den andre linjen inneholder et heltall $N$, som representerer at det finnes $N$ typer forhåndsbestemte operasjoner.
• Den $i$-te linjen av de følgende $N$ linjene ($1 \le i \le N$) inneholder heltallene $L_i, R_i$ adskilt med mellomrom. Dette representerer at den $i$-te operasjonen er å "snu alle kort fra det $L_i$-te kortet til det $R_i$-te kortet fra venstre".

Utdata

Hvis det er mulig å gjøre spådommen vellykket, skriv ut den minste tiden som kreves for å gjøre den vellykket som et heltall på en enkelt linje. Ellers, skriv ut -1.

Begrensninger

Alle inndata tilfredsstiller følgende betingelser:

• $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$).

Deloppgaver

Deloppgave 1 [15 poeng]

• $N \le 10$ er oppfylt.

Deloppgave 2 [50 poeng]

• Følgende betingelser er oppfylt:
  • $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$.

Deloppgave 3 [35 poeng]

• Det er ingen ytterligere begrensninger.

Eksempler

Inndata 1

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

Utdata 1

12

Forklaring 1

Til å begynne med ligger kortene som IOOIIIOOOOIIIII. Å utføre den 2. operasjonen resulterer i IIIOOOOOOOIIIII. Denne operasjonen tar 5 sekunder. Å deretter utføre den 3. operasjonen resulterer i IIIIIIIIIIIIIII, og spådommen er vellykket. Denne operasjonen tar 7 sekunder. Spådommen kan gjøres vellykket på 12 sekunder. Siden dette er minimumsverdien, skriv ut 12.

Inndata 2

1 1 1 1 1
1
1 1

Utdata 2

-1

Forklaring 2

I dette inndataeksempelet kan ikke spådommen gjøres vellykket, så skriv ut -1.