Le président K aime la divination et en pratique toujours différentes formes. Aujourd'hui, il a décidé de prédire les résultats de la délégation japonaise aux IOI de cette année à l'aide de cartes portant I au recto et O au verso.

La méthode de divination est la suivante.

1. On choisit d'abord des entiers strictement positifs $A,B,C,D,E$.
2. On dispose $A+B+C+D+E$ cartes sur une ligne horizontale. En partant de la gauche, les $A$ premières cartes sont posées recto visible, les $B$ suivantes verso visible, les $C$ suivantes recto visible, les $D$ suivantes verso visible et les $E$ suivantes recto visible. On obtient donc, de gauche à droite, $A$ caractères I, $B$ caractères O, $C$ caractères I, $D$ caractères O et $E$ caractères I.
3. On choisit une ou plusieurs opérations parmi $N$ types d'opérations définis à l'avance, puis on les effectue dans l'ordre souhaité. On peut effectuer plusieurs fois le même type d'opération. L'opération de type $i$ ($1 \le i \le N$) consiste à retourner toutes les cartes de la $L_i$-ième à la $R_i$-ième en partant de la gauche. Retourner une carte prend une seconde. L'opération de type $i$ prend donc $R_i-L_i+1$ secondes.
4. Si toutes les cartes sont recto visible une fois les opérations terminées, la divination est réussie.

Pour éviter de retourner les cartes plus que nécessaire, le président K a décidé, avant de pratiquer réellement cette divination, de déterminer d'abord s'il est possible de la réussir. Si c'est possible, il souhaite aussi déterminer le temps minimal nécessaire pour la réussir.

Tâche

On vous donne les informations sur la disposition des cartes et les opérations définies à l'avance. Écrivez un programme qui détermine s'il est possible de réussir la divination et, si c'est possible, le temps minimal nécessaire.

Entrée

Lisez les données suivantes sur l'entrée standard.

• La première ligne contient les entiers $A,B,C,D,E$ séparés par des espaces. Cela signifie qu'au début de la divination, on dispose, de gauche à droite, $A$ cartes recto visible, puis $B$ cartes verso visible, $C$ cartes recto visible, $D$ cartes verso visible et $E$ cartes recto visible.
• La deuxième ligne contient un entier $N$, indiquant qu'il existe $N$ types d'opérations définis à l'avance.
• La $i$-ième des $N$ lignes suivantes ($1 \le i \le N$) contient les entiers $L_i,R_i$ séparés par une espace. Cela signifie que l'opération de type $i$ consiste à retourner toutes les cartes de la $L_i$-ième à la $R_i$-ième en partant de la gauche.

Sortie

S'il est possible de réussir la divination, écrivez sur une ligne de la sortie standard un entier représentant le temps minimal nécessaire pour la réussir. Sinon, écrivez -1.

Contraintes

Toutes les données d'entrée satisfont les conditions suivantes.

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

Sous-tâches

Sous-tâche 1 [15 points]

• $N \le 10$.

Sous-tâche 2 [50 points]

Les conditions suivantes sont satisfaites.

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

Sous-tâche 3 [35 points]

Il n'y a pas de contrainte supplémentaire.

Exemples

Entrée 1

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

Sortie 1

12

Remarque

Au début, les cartes sont disposées comme suit : IOOIIIOOOOIIIII.

Après l'opération de type $2$, on obtient IIIOOOOOOOIIIII. Cette opération prend $5$ secondes.

Ensuite, après l'opération de type $3$, on obtient IIIIIIIIIIIIIII et la divination est réussie. Cette opération prend $7$ secondes.

On peut réussir la divination en $12$ secondes. Comme c'est le minimum, on écrit $12$.

Entrée 2

1 1 1 1 1
1
1 1

Sortie 2

-1

Remarque

Dans cet exemple, il est impossible de réussir la divination, donc on écrit -1.