ประธาน K ชอบการทำนายดวงและมักทำนายด้วยวิธีต่าง ๆ วันนี้เขาตัดสินใจใช้ไพ่ที่ด้านหน้าเขียน I และด้านหลังเขียน O เพื่อทำนายผลงานของทีมญี่ปุ่นในการแข่งขัน IOI ปีนี้

วิธีทำนายเป็นดังนี้

1. ก่อนอื่น กำหนดจำนวนเต็มบวก $A,B,C,D,E$
2. วางไพ่ $A+B+C+D+E$ ใบเรียงเป็นแถวแนวนอน โดยไพ่ $A$ ใบแรกจากซ้ายหงายหน้า ไพ่ $B$ ใบถัดมาคว่ำหน้า ไพ่ $C$ ใบถัดมาหงายหน้า ไพ่ $D$ ใบถัดมาคว่ำหน้า และไพ่ $E$ ใบถัดมาหงายหน้า เมื่อเรียงเช่นนี้ จากซ้ายไปขวาจะมี I จำนวน $A$ ตัว ตามด้วย O จำนวน $B$ ตัว ตามด้วย I จำนวน $C$ ตัว ตามด้วย O จำนวน $D$ ตัว และตามด้วย I จำนวน $E$ ตัว
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

เมื่อทำการดำเนินการประเภทที่สอง ไพ่จะเรียงเป็น IIIOOOOOOOIIIII การดำเนินการนี้ใช้เวลา $5$ วินาที

จากนั้น เมื่อทำการดำเนินการประเภทที่สาม ไพ่จะเรียงเป็น IIIIIIIIIIIIIII และทำให้การทำนายสำเร็จ การดำเนินการนี้ใช้เวลา $7$ วินาที

สามารถทำให้การทำนายสำเร็จได้ภายใน $12$ วินาที และค่านี้น้อยที่สุด จึงเขียน $12$

ข้อมูลนำเข้า 2

1 1 1 1 1
1
1 1

ข้อมูลส่งออก 2

-1

หมายเหตุ

ในตัวอย่างนี้ ไม่สามารถทำให้การทำนายสำเร็จได้ จึงเขียน $-1$