يحب رئيس مجلس الإدارة 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$ من اليسار». يستغرق قلب بطاقة واحدة ثانية واحدة. لذلك يستغرق تنفيذ العملية من النوع $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$.