היושב ראש 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$ משמאל״. הפיכת קלף אחד אורכת שנייה אחת. לכן ביצוע פעולה מסוג $i$ אורך $R_i-L_i+1$ שניות.
4. לאחר סיום הפעולות, אם כל הקלפים מונחים עם הפנים כלפי מעלה, ניחוש העתידות נחשב מוצלח.

כדי להימנע מהפיכת קלפים מעבר לנדרש, היושב ראש K החליט לבדוק תחילה אם אפשר לגרום לניחוש להצליח, לפני שיבצע אותו בפועל עם קלפים. נוסף על כך, אם הדבר אפשרי, הוא רוצה למצוא את הזמן המזערי הדרוש לכך.

המשימה

נתונים מידע על סידור הקלפים ומידע על הפעולות שנקבעו מראש. כתבו תוכנית הקובעת אם אפשר לגרום לניחוש להצליח, ואם כן, מוצאת את הזמן המזערי הדרוש לכך.

קלט

קראו את הנתונים הבאים מהקלט התקני.

• השורה הראשונה מכילה את המספרים השלמים $A,B,C,D,E$, מופרדים ברווחים. פירוש הדבר שבתחילת הניחוש מסדרים את הקלפים כך שמשמאל, $A$ הקלפים הראשונים מונחים עם הפנים כלפי מעלה, $B$ הבאים עם הגב כלפי מעלה, $C$ הבאים עם הפנים כלפי מעלה, $D$ הבאים עם הגב כלפי מעלה ו־$E$ הבאים עם הפנים כלפי מעלה.
• השורה השנייה מכילה מספר שלם $N$. הוא מציין שיש $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.

לאחר ביצוע פעולה מסוג 2, מתקבל IIIOOOOOOOIIIII. פעולה זו אורכת 5 שניות.

לאחר מכן, ביצוע פעולה מסוג 3 נותן IIIIIIIIIIIIIII, וכך אפשר לגרום לניחוש להצליח. פעולה זו אורכת 7 שניות.

אפשר לגרום לניחוש להצליח תוך 12 שניות. מכיוון שזהו הזמן המזערי, יש להדפיס 12.

קלט 2

1 1 1 1 1
1
1 1

פלט 2

-1

הסבר

בדוגמה זו אי אפשר לגרום לניחוש להצליח, ולכן יש להדפיס $-1$.