Председатель K любит гадания и постоянно пробует разные их виды. Сегодня он решил предсказать выступление японской сборной на IOI этого года с помощью карточек, у которых на лицевой стороне написана буква I, а на оборотной — O.

Гадание проводится следующим образом.

1. Сначала выбираются положительные целые числа $A,B,C,D,E$.
2. В один горизонтальный ряд выкладываются $A+B+C+D+E$ карточек. Первые $A$ карточек слева кладутся лицевой стороной вверх, следующие $B$ — оборотной, следующие $C$ — лицевой, следующие $D$ — оборотной, а следующие $E$ — лицевой. Таким образом, слева направо видны $A$ букв I, $B$ букв O, $C$ букв I, $D$ букв O и $E$ букв I.
3. Из $N$ заранее заданных типов операций выбирается одна или несколько операций, которые выполняются в произвольном порядке. Один тип операции можно выполнять несколько раз. Операция типа $i$ ($1 \le i \le N$) переворачивает все карточки с $L_i$-й по $R_i$-ю слева включительно. Переворот одной карточки занимает 1 секунду. Поэтому операция типа $i$ занимает $R_i-L_i+1$ секунд.
4. Если после выполнения операций все карточки лежат лицевой стороной вверх, гадание считается успешным.

Чтобы не переворачивать карточки больше необходимого, председатель K решил ещё до самого гадания выяснить, возможно ли сделать его успешным. Если это возможно, он также хочет узнать минимальное время, необходимое для успешного гадания.

Задача

Даны сведения о начальном расположении карточек и заранее заданных операциях. Напишите программу, которая определяет, возможно ли успешное гадание, и, если возможно, находит минимальное необходимое время.

Входные данные

Считайте следующие данные со стандартного ввода.

• Первая строка содержит целые числа $A,B,C,D,E$, разделённые пробелами. Они означают, что в начале гадания первые $A$ карточек слева лежат лицевой стороной вверх, следующие $B$ — оборотной, следующие $C$ — лицевой, следующие $D$ — оборотной, а следующие $E$ — лицевой.
• Вторая строка содержит целое число $N$, означающее количество заранее заданных типов операций.
• $i$-я строка ($1 \le i \le N$) из следующих $N$ строк содержит целые числа $L_i,R_i$, разделённые пробелом. Это означает, что операция типа $i$ переворачивает все карточки с $L_i$-й по $R_i$-ю слева включительно.

Выходные данные

Если успешное гадание возможно, выведите в одной строке стандартного вывода целое число — минимальное время, необходимое для успешного гадания. В противном случае выведите $-1$.

Ограничения

Все входные данные удовлетворяют следующим условиям.

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

Подзадачи

Подзадача 1 [15 баллов]

• Выполняется $N \le 10$.

Подзадача 2 [50 баллов]

Выполняются следующие условия.

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

Подзадача 3 [35 баллов]

Дополнительных ограничений нет.

Примеры

Входные данные 1

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

Выходные данные 1

12

Примечание

Изначально карточки образуют строку IOOIIIOOOOIIIII.

После операции второго типа получается IIIOOOOOOOIIIII. Эта операция занимает 5 секунд.

Затем после операции третьего типа получается IIIIIIIIIIIIIII, и гадание становится успешным. Эта операция занимает 7 секунд.

Успешное гадание можно провести за 12 секунд. Это минимальное время, поэтому следует вывести $12$.

Входные данные 2

1 1 1 1 1
1
1 1

Выходные данные 2

-1

Примечание

В этом примере успешное гадание невозможно, поэтому следует вывести $-1$.