O presidente K gosta de adivinhação e está sempre experimentando vários métodos. Hoje, decidiu prever o desempenho da delegação japonesa na IOI deste ano usando cartas com I na frente e O no verso.

O método de adivinhação é o seguinte.

1. Primeiro, escolher inteiros positivos $A,B,C,D,E$.
2. Dispor $A+B+C+D+E$ cartas em uma única fila horizontal. Da esquerda para a direita, as primeiras $A$ cartas ficam com a frente para cima, as próximas $B$ com o verso para cima, as próximas $C$ com a frente para cima, as próximas $D$ com o verso para cima e as últimas $E$ com a frente para cima. Assim, da esquerda para a direita, aparecem $A$ caracteres I, $B$ caracteres O, $C$ caracteres I, $D$ caracteres O e $E$ caracteres I.
3. Escolher uma ou mais operações entre $N$ tipos predeterminados e realizá-las na ordem desejada. É permitido realizar o mesmo tipo de operação duas ou mais vezes. A operação do tipo $i$ ($1 \le i \le N$) consiste em virar todas as cartas da posição $L_i$ até a posição $R_i$, contando da esquerda. Virar uma carta leva 1 segundo. Portanto, realizar a operação do tipo $i$ leva $R_i-L_i+1$ segundos.
4. Após terminar as operações, a adivinhação é bem-sucedida se todas as cartas estiverem com a frente para cima.

Para evitar virar cartas mais vezes do que o necessário, o presidente K decidiu determinar primeiro se é possível fazer a adivinhação ser bem-sucedida, antes de usar as cartas de verdade. Além disso, se for possível, decidiu determinar o tempo mínimo necessário para isso.

Tarefa

São fornecidas informações sobre a disposição das cartas e sobre as operações predeterminadas. Escreva um programa que determine se é possível fazer a adivinhação ser bem-sucedida e, caso seja, calcule o tempo mínimo necessário.

Entrada

Leia os seguintes dados da entrada padrão.

• A primeira linha contém os inteiros $A,B,C,D,E$, separados por espaços. Isso indica que, inicialmente, da esquerda para a direita, as primeiras $A$ cartas ficam com a frente para cima, as próximas $B$ com o verso para cima, as próximas $C$ com a frente para cima, as próximas $D$ com o verso para cima e as últimas $E$ com a frente para cima.
• A segunda linha contém o inteiro $N$, indicando que existem $N$ tipos de operações predeterminadas.
• A $i$-ésima linha ($1 \le i \le N$) das próximas $N$ linhas contém os inteiros $L_i,R_i$, separados por um espaço. Isso indica que a operação do tipo $i$ consiste em virar todas as cartas da posição $L_i$ até a posição $R_i$, contando da esquerda.

Saída

Se for possível fazer a adivinhação ser bem-sucedida, escreva em uma linha da saída padrão um inteiro que represente o tempo mínimo necessário. Caso contrário, escreva $-1$.

Restrições

Todos os dados de entrada satisfazem as seguintes condições.

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

Subtarefas

Subtarefa 1 [15 pontos]

• Vale $N \le 10$.

Subtarefa 2 [50 pontos]

As seguintes condições são satisfeitas.

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

Subtarefa 3 [35 pontos]

Não há restrições adicionais.

Exemplos

Entrada 1

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

Saída 1

12

Observação

Inicialmente, as cartas estão dispostas como IOOIIIOOOOIIIII.

Após realizar a operação do tipo 2, a disposição passa a ser IIIOOOOOOOIIIII. Essa operação leva 5 segundos.

Em seguida, a operação do tipo 3 transforma a disposição em IIIIIIIIIIIIIII, fazendo a adivinhação ser bem-sucedida. Essa operação leva 7 segundos.

É possível fazer a adivinhação ser bem-sucedida em 12 segundos. Como esse é o mínimo, escrevemos 12.

Entrada 2

1 1 1 1 1
1
1 1

Saída 2

-1

Observação

Neste exemplo, não é possível fazer a adivinhação ser bem-sucedida, por isso escrevemos $-1$.