Директор K бал ашуды жақсы көреді және жиі түрлі болжамдар жасайды. Бүгін ол алдыңғы бетінде 'I' және артқы бетінде 'O' жазылған карталарды пайдаланып, биылғы IOI-да Жапония құрамасының өнер көрсетуін болжауды ұйғарды.

Бал ашу әдісі келесідей:

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$ түрі бар екенін білдіретін $N$ бүтін саны берілген.
• Келесі $N$ қатардың $i$-ші қатарында ($1 \le i \le 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

Ескертпе 1

Бастапқыда карталар IOOIIIOOOOIIIII түрінде орналасқан. 2-ші амалды орындау IIIOOOOOOOIIIII нәтижесін береді. Бұл амалға 5 секунд кетеді. Одан кейін 3-ші амалды орындау IIIIIIIIIIIIIII нәтижесін береді және бал ашу сәтті болады. Бұл амалға 7 секунд кетеді. Бал ашуды 12 секундта сәтті аяқтауға болады. Бұл ең кіші мән болғандықтан, 12 шығарыңыз.

Кіріс 2

1 1 1 1 1
1
1 1

Шығыс 2

-1

Ескертпе 2

Бұл кіріс мысалында бал ашуды сәтті жасау мүмкін емес, сондықтан -1 шығарыңыз.