Голова 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$.