Al presidente K le gusta la adivinación y siempre practica distintas formas de ella. Hoy ha decidido predecir el desempeño de la delegación japonesa en la IOI de este año utilizando cartas con una I en el anverso y una O en el reverso.

El procedimiento de adivinación es el siguiente.

1. Primero, elige los enteros positivos $A,B,C,D,E$.
2. Coloca $A+B+C+D+E$ cartas en una fila horizontal. De izquierda a derecha, las primeras $A$ cartas se colocan con el anverso hacia arriba; las siguientes $B$, con el reverso hacia arriba; las siguientes $C$, con el anverso hacia arriba; las siguientes $D$, con el reverso hacia arriba; y las últimas $E$, con el anverso hacia arriba. Así, de izquierda a derecha aparecen $A$ letras I, $B$ letras O, $C$ letras I, $D$ letras O y $E$ letras I.
3. Elige una o más operaciones entre $N$ tipos de operaciones predeterminados y realízalas en el orden que quieras. Se permite realizar dos o más veces el mismo tipo de operación. La operación de tipo $i$ ($1 \le i \le N$) consiste en dar la vuelta a todas las cartas desde la posición $L_i$ hasta la posición $R_i$, contando desde la izquierda. Dar la vuelta a una carta tarda 1 segundo. Por tanto, realizar la operación de tipo $i$ tarda $R_i-L_i+1$ segundos.
4. Si, al terminar las operaciones, todas las cartas tienen el anverso hacia arriba, la adivinación tiene éxito.

Para evitar dar la vuelta a las cartas más veces de las necesarias, el presidente K ha decidido averiguar primero si es posible lograr que la adivinación tenga éxito, antes de practicarla con las cartas reales. Además, si es posible, quiere calcular el tiempo mínimo necesario para conseguirlo.

Tarea

Se proporciona la información sobre la disposición de las cartas y las operaciones predeterminadas. Escribe un programa que determine si es posible lograr que la adivinación tenga éxito y, en caso afirmativo, calcule el tiempo mínimo necesario para ello.

Entrada

Lee los siguientes datos de la entrada estándar.

• La primera línea contiene los enteros $A,B,C,D,E$, separados por espacios. Esto indica que, al principio de la adivinación, de izquierda a derecha se colocan $A$ cartas con el anverso hacia arriba, luego $B$ con el reverso hacia arriba, luego $C$ con el anverso hacia arriba, luego $D$ con el reverso hacia arriba y, por último, $E$ con el anverso hacia arriba.
• La segunda línea contiene un entero $N$, que indica que hay $N$ tipos de operaciones predeterminados.
• La línea $i$ ($1 \le i \le N$) de las siguientes $N$ líneas contiene los enteros $L_i,R_i$, separados por un espacio. Indican que la operación de tipo $i$ consiste en dar la vuelta a todas las cartas desde la posición $L_i$ hasta la posición $R_i$, contando desde la izquierda.

Salida

Si es posible lograr que la adivinación tenga éxito, escribe en una línea de la salida estándar un entero que represente el tiempo mínimo necesario para ello. En caso contrario, escribe $-1$.

Restricciones

Todos los datos de entrada cumplen las siguientes condiciones.

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

Subtareas

Subtarea 1 [15 puntos]

• Se cumple $N \le 10$.

Subtarea 2 [50 puntos]

Se cumplen las siguientes condiciones.

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

Subtarea 3 [35 puntos]

No hay restricciones adicionales.

Ejemplos

Entrada 1

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

Salida 1

12

Nota

Inicialmente, las cartas están dispuestas como IOOIIIOOOOIIIII.

Al realizar la operación de tipo 2, quedan como IIIOOOOOOOIIIII. Esta operación tarda 5 segundos.

A continuación, al realizar la operación de tipo 3, quedan como IIIIIIIIIIIIIII, y la adivinación tiene éxito. Esta operación tarda 7 segundos.

Es posible lograr que la adivinación tenga éxito en 12 segundos. Como este es el mínimo, se escribe 12.

Entrada 2

1 1 1 1 1
1
1 1

Salida 2

-1

Nota

En este ejemplo no es posible lograr que la adivinación tenga éxito, por lo que se escribe -1.