Il direttore K ama la divinazione e pratica spesso vari tipi di predizione. Oggi ha deciso di prevedere i risultati della squadra giapponese alle IOI di quest'anno utilizzando delle carte con 'I' sul fronte e 'O' sul retro.

Il metodo di divinazione è il seguente:

1. Per prima cosa, si scelgono degli interi positivi $A, B, C, D, E$.
2. Si dispongono $A + B + C + D + E$ carte in un'unica fila. A questo punto, si dispongono $A$ carte scoperte (a faccia in su), seguite da $B$ carte coperte (a faccia in giù), seguite da $C$ carte scoperte, seguite da $D$ carte coperte e infine $E$ carte scoperte. Disponendole in questo modo si ottiene una sequenza di $A$ 'I', $B$ 'O', $C$ 'I', $D$ 'O' ed $E$ 'I' da sinistra a destra.
3. Si scelgono una o più operazioni tra $N$ tipi predeterminati e si eseguono in qualsiasi ordine. È possibile eseguire lo stesso tipo di operazione due o più volte. L'$i$-esimo tipo di operazione ($1 \le i \le N$) consiste nel "girare tutte le carte dalla $L_i$-esima carta alla $R_i$-esima carta partendo da sinistra". Girare una carta richiede 1 secondo. Pertanto, eseguire la $i$-esima operazione richiede $R_i - L_i + 1$ secondi.
4. Al termine delle operazioni, la divinazione ha successo se tutte le carte sono scoperte.

Per evitare di girare le carte più del necessario, il direttore K ha deciso di determinare se sia possibile far riuscire la divinazione prima di utilizzare effettivamente le carte. Inoltre, se è possibile far riuscire la divinazione, ha deciso di trovare il tempo minimo necessario per farlo.

Compito

Date le informazioni sulla disposizione delle carte e sulle operazioni predeterminate, scrivi un programma per determinare se sia possibile far riuscire la divinazione e, in tal caso, trovare il tempo minimo necessario per farla riuscire.

Formato di input

Leggi i seguenti dati dallo standard input:

• La prima riga contiene gli interi $A, B, C, D, E$ separati da spazi. Questo rappresenta il fatto che all'inizio della divinazione ci sono $A$ carte scoperte, seguite da $B$ carte coperte, seguite da $C$ carte scoperte, seguite da $D$ carte coperte ed $E$ carte scoperte.
• La seconda riga contiene un intero $N$, che rappresenta la presenza di $N$ tipi di operazioni predeterminate.
• La $i$-esima riga delle successive $N$ righe ($1 \le i \le N$) contiene gli interi $L_i, R_i$ separati da spazi. Questo rappresenta il fatto che la $i$-esima operazione consiste nel "girare tutte le carte dalla $L_i$-esima carta alla $R_i$-esima carta partendo da sinistra".

Formato di output

Se è possibile far riuscire la divinazione, stampa il tempo minimo necessario per farla riuscire come un intero su una singola riga. Altrimenti, stampa -1.

Vincoli

Tutti i dati di input soddisfano le seguenti condizioni:

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

Sottoproblemi

Sottoproblema 1 [15 punti]

• È soddisfatta la condizione $N \le 10$.

Sottoproblema 2 [50 punti]

• Sono soddisfatte le seguenti condizioni:
  • $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$.

Sottoproblema 3 [35 punti]

• Non ci sono vincoli aggiuntivi.

Esempi

Input 1

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

Output 1

12

Nota 1

Inizialmente, le carte sono disposte come IOOIIIOOOOIIIII. Eseguendo la 2ª operazione si ottiene IIIOOOOOOOIIIII. Questa operazione richiede 5 secondi. Successivamente, eseguendo la 3ª operazione si ottiene IIIIIIIIIIIIIII, e la divinazione ha successo. Questa operazione richiede 7 secondi. La divinazione può avere successo in 12 secondi. Poiché questo è il valore minimo, stampa 12.

Input 2

1 1 1 1 1
1
1 1

Output 2

-1

Nota 2

In questo esempio di input, non è possibile far riuscire la divinazione, quindi stampa -1.