Przewodniczący K lubi wróżby i stale próbuje różnych sposobów wróżenia. Dzisiaj postanowił przewidzieć wyniki japońskiej reprezentacji na tegorocznej IOI za pomocą kart z literą I na awersie i literą O na rewersie.

Wróżba przebiega następująco:

1. Najpierw wybiera dodatnie liczby całkowite $A,B,C,D,E$.
2. Układa $A+B+C+D+E$ kart w jednym rzędzie. Pierwsze $A$ kart od lewej leży awersem do góry, kolejne $B$ rewersem do góry, kolejne $C$ awersem do góry, kolejne $D$ rewersem do góry, a ostatnie $E$ awersem do góry. W ten sposób od lewej widać kolejno $A$ liter I, $B$ liter O, $C$ liter I, $D$ liter O i $E$ liter I.
3. Wybiera co najmniej jedną operację spośród $N$ ustalonych wcześniej rodzajów i wykonuje je w dowolnej kolejności. Ten sam rodzaj operacji można wykonać więcej niż raz. Operacja rodzaju $i$ ($1 \le i \le N$) polega na odwróceniu wszystkich kart od $L_i$-tej do $R_i$-tej od lewej. Odwrócenie jednej karty trwa $1$ sekundę, więc wykonanie operacji rodzaju $i$ zajmuje $R_i-L_i+1$ sekund.
4. Wróżba kończy się powodzeniem, jeśli po wykonaniu operacji wszystkie karty leżą awersem do góry.

Aby nie odwracać kart więcej razy, niż to konieczne, przewodniczący K postanowił przed rozpoczęciem właściwej wróżby sprawdzić, czy w ogóle może ona zakończyć się powodzeniem. Jeśli jest to możliwe, chce również znaleźć najkrótszy czas potrzebny do uzyskania powodzenia.

Zadanie

Dane są informacje o początkowym ułożeniu kart oraz o ustalonych wcześniej operacjach. Napisz program, który sprawdzi, czy wróżba może zakończyć się powodzeniem, a jeśli tak, obliczy najkrótszy potrzebny do tego czas.

Wejście

Wczytaj następujące dane ze standardowego wejścia.

• Pierwszy wiersz zawiera liczby całkowite $A,B,C,D,E$ oddzielone spacjami. Oznacza to, że na początku wróżby pierwsze $A$ kart od lewej leży awersem do góry, kolejne $B$ rewersem do góry, kolejne $C$ awersem do góry, kolejne $D$ rewersem do góry, a ostatnie $E$ awersem do góry.
• Drugi wiersz zawiera liczbę całkowitą $N$, oznaczającą liczbę ustalonych wcześniej rodzajów operacji.
• W $i$-tym ($1 \le i \le N$) spośród kolejnych $N$ wierszy znajdują się liczby całkowite $L_i,R_i$ oddzielone spacją. Operacja rodzaju $i$ polega na odwróceniu wszystkich kart od $L_i$-tej do $R_i$-tej od lewej.

Wyjście

Jeśli wróżba może zakończyć się powodzeniem, wypisz w jednym wierszu standardowego wyjścia liczbę całkowitą równą najkrótszemu potrzebnemu czasowi. W przeciwnym razie wypisz -1.

Ograniczenia

Wszystkie dane wejściowe spełniają następujące warunki.

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

Podzadania

Podzadanie 1 [15 punktów]

• $N \le 10$.

Podzadanie 2 [50 punktów]

Spełnione są następujące warunki.

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

Podzadanie 3 [35 punktów]

Brak dodatkowych ograniczeń.

Przykład

Wejście 1

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

Wyjście 1

12

Uwagi

Początkowe ułożenie kart to IOOIIIOOOOIIIII.

Po wykonaniu operacji drugiego rodzaju otrzymujemy IIIOOOOOOOIIIII. Operacja trwa $5$ sekund.

Następnie wykonanie operacji trzeciego rodzaju daje IIIIIIIIIIIIIII, dzięki czemu wróżba kończy się powodzeniem. Ta operacja trwa $7$ sekund.

Powodzenie można uzyskać w $12$ sekund. Jest to najkrótszy możliwy czas, więc wypisujemy $12$.

Wejście 2

1 1 1 1 1
1
1 1

Wyjście 2

-1

Uwagi

W tym przykładzie wróżba nie może zakończyć się powodzeniem, więc wypisujemy -1.