Vorsitzender K mag Wahrsagerei und probiert ständig verschiedene Methoden aus. Heute hat er beschlossen, mit Karten, auf deren Vorderseite I und auf deren Rückseite O steht, die Leistung der japanischen Mannschaft bei der diesjährigen IOI vorherzusagen.

Die Methode funktioniert wie folgt.

1. Zunächst werden positive ganze Zahlen $A,B,C,D,E$ festgelegt.
2. $A+B+C+D+E$ Karten werden nebeneinander in einer Reihe ausgelegt. Von links liegen die ersten $A$ Karten mit der Vorderseite nach oben, die nächsten $B$ mit der Rückseite, die nächsten $C$ mit der Vorderseite, die nächsten $D$ mit der Rückseite und die letzten $E$ mit der Vorderseite nach oben. So stehen von links nach rechts $A$ Zeichen I, $B$ Zeichen O, $C$ Zeichen I, $D$ Zeichen O und $E$ Zeichen I in der Reihe.
3. Aus $N$ vorgegebenen Arten von Operationen werden eine oder mehrere Operationen ausgewählt und in beliebiger Reihenfolge ausgeführt. Dabei darf dieselbe Art von Operation auch mehrmals ausgeführt werden. Die $i$-te Art ($1 \le i \le N$) besteht darin, alle Karten von der $L_i$-ten bis zur $R_i$-ten Karte von links umzudrehen. Das Umdrehen einer Karte dauert $1$ Sekunde. Daher dauert eine Operation der $i$-ten Art $R_i-L_i+1$ Sekunden.
4. Wenn nach Abschluss der Operationen alle Karten mit der Vorderseite nach oben liegen, ist die Wahrsagung erfolgreich.

Damit er die Karten nicht häufiger als nötig umdreht, möchte Vorsitzender K zunächst feststellen, ob eine erfolgreiche Wahrsagung überhaupt möglich ist, bevor er tatsächlich Karten verwendet. Falls sie möglich ist, möchte er außerdem die kleinste dafür benötigte Zeit bestimmen.

Aufgabe

Gegeben sind die Anordnung der Karten und die vorgegebenen Operationen. Schreibe ein Programm, das bestimmt, ob eine erfolgreiche Wahrsagung möglich ist, und gegebenenfalls die kleinste dafür benötigte Zeit berechnet.

Eingabe

Lies die folgenden Daten von der Standardeingabe ein.

• Die erste Zeile enthält die durch Leerzeichen getrennten ganzen Zahlen $A,B,C,D,E$. Sie geben an, dass zu Beginn von links die ersten $A$ Karten mit der Vorderseite nach oben liegen, die nächsten $B$ mit der Rückseite, die nächsten $C$ mit der Vorderseite, die nächsten $D$ mit der Rückseite und die letzten $E$ mit der Vorderseite nach oben.
• Die zweite Zeile enthält eine ganze Zahl $N$. Sie gibt an, dass $N$ Arten von Operationen vorgegeben sind.
• Die $i$-te der folgenden $N$ Zeilen ($1 \le i \le N$) enthält die durch ein Leerzeichen getrennten ganzen Zahlen $L_i,R_i$. Sie geben an, dass eine Operation der $i$-ten Art alle Karten von der $L_i$-ten bis zur $R_i$-ten Karte von links umdreht.

Ausgabe

Falls eine erfolgreiche Wahrsagung möglich ist, gib in einer Zeile auf der Standardausgabe eine ganze Zahl aus, die die kleinste dafür benötigte Zeit angibt. Andernfalls gib $-1$ aus.

Beschränkungen

Alle Eingabedaten erfüllen die folgenden Bedingungen.

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

Teilaufgaben

Teilaufgabe 1 [15 Punkte]

• $N \le 10$.

Teilaufgabe 2 [50 Punkte]

Die folgenden Bedingungen gelten.

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

Teilaufgabe 3 [35 Punkte]

Es gibt keine zusätzlichen Beschränkungen.

Beispiele

Eingabe 1

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

Ausgabe 1

12

Hinweis

Anfangs sind die Karten als IOOIIIOOOOIIIII angeordnet.

Nach einer Operation der zweiten Art lautet die Anordnung IIIOOOOOOOIIIII. Diese Operation dauert $5$ Sekunden.

Nach einer anschließenden Operation der dritten Art lautet sie IIIIIIIIIIIIIII, womit die Wahrsagung erfolgreich ist. Diese Operation dauert $7$ Sekunden.

Die Wahrsagung kann also in $12$ Sekunden erfolgreich durchgeführt werden. Da dies die kleinste mögliche Zeit ist, gib 12 aus.

Eingabe 2

1 1 1 1 1
1
1 1

Ausgabe 2

-1

Hinweis

In diesem Beispiel ist keine erfolgreiche Wahrsagung möglich, also gib -1 aus.