Chủ tịch K thích bói toán và luôn thử nhiều cách bói khác nhau. Hôm nay, ông quyết định dùng các lá bài có chữ I ở mặt trước và chữ O ở mặt sau để bói thành tích của đoàn Nhật Bản tại IOI năm nay.

Cách bói như sau.

1. Trước tiên, chọn các số nguyên dương $A,B,C,D,E$.
2. Xếp $A+B+C+D+E$ lá bài thành một hàng ngang. Tính từ trái sang, $A$ lá đầu ngửa mặt trước, $B$ lá tiếp theo ngửa mặt sau, $C$ lá tiếp theo ngửa mặt trước, $D$ lá tiếp theo ngửa mặt sau, và $E$ lá tiếp theo ngửa mặt trước. Khi xếp như vậy, từ trái sang sẽ có $A$ chữ I, $B$ chữ O, $C$ chữ I, $D$ chữ O, và $E$ chữ I.
3. Chọn một hoặc nhiều thao tác trong $N$ loại thao tác đã định trước và thực hiện theo thứ tự tùy ý. Có thể thực hiện cùng một loại thao tác từ hai lần trở lên. Thao tác loại thứ $i$ ($1 \le i \le N$) là “lật tất cả các lá bài từ lá thứ $L_i$ đến lá thứ $R_i$ tính từ trái sang”. Lật một lá bài mất 1 giây. Vì vậy, thực hiện thao tác loại thứ $i$ mất $R_i-L_i+1$ giây.
4. Sau khi thực hiện các thao tác, nếu mọi lá bài đều ngửa mặt trước thì việc bói được coi là thành công.

Để tránh lật bài nhiều hơn cần thiết, trước khi bói bằng các lá bài thật, chủ tịch K quyết định xác định xem có thể làm cho việc bói thành công hay không. Hơn nữa, nếu có thể, ông muốn tìm thời gian ít nhất cần thiết để thành công.

Yêu cầu

Cho thông tin về cách xếp các lá bài và các thao tác đã định trước. Hãy viết chương trình xác định xem có thể làm cho việc bói thành công hay không, và nếu có thể thì tìm thời gian ít nhất cần thiết.

Dữ liệu vào

Đọc dữ liệu sau từ đầu vào chuẩn.

• Dòng đầu chứa các số nguyên $A,B,C,D,E$ cách nhau bởi dấu cách. Điều này có nghĩa khi bắt đầu bói, từ trái sang, $A$ lá đầu ngửa mặt trước, $B$ lá tiếp theo ngửa mặt sau, $C$ lá tiếp theo ngửa mặt trước, $D$ lá tiếp theo ngửa mặt sau, và $E$ lá tiếp theo ngửa mặt trước.
• Dòng thứ hai chứa số nguyên $N$. Điều này có nghĩa có $N$ loại thao tác đã định trước.
• Dòng thứ $i$ ($1 \le i \le N$) trong $N$ dòng tiếp theo chứa các số nguyên $L_i,R_i$ cách nhau bởi dấu cách. Điều này có nghĩa thao tác loại thứ $i$ là “lật tất cả các lá bài từ lá thứ $L_i$ đến lá thứ $R_i$ tính từ trái sang”.

Dữ liệu ra

Nếu có thể làm cho việc bói thành công, hãy ghi một số nguyên biểu thị thời gian ít nhất cần thiết trên một dòng của đầu ra chuẩn. Nếu không, hãy ghi -1.

Giới hạn

Tất cả dữ liệu vào thỏa mãn các điều kiện sau.

• $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$).

Nhiệm vụ con

Nhiệm vụ con 1 [15 điểm]

• $N \le 10$.

Nhiệm vụ con 2 [50 điểm]

Thỏa mãn các điều kiện sau.

• $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$.

Nhiệm vụ con 3 [35 điểm]

Không có giới hạn bổ sung.

Ví dụ

Dữ liệu vào 1

1 2 3 4 5
3
2 3
2 6
4 10

Dữ liệu ra 1

12

Ghi chú

Ban đầu, các lá bài được xếp thành IOOIIIOOOOIIIII.

Khi thực hiện thao tác loại thứ hai, ta được IIIOOOOOOOIIIII. Thao tác này mất 5 giây.

Tiếp theo, thực hiện thao tác loại thứ ba sẽ được IIIIIIIIIIIIIII, và việc bói thành công. Thao tác này mất 7 giây.

Có thể làm cho việc bói thành công trong 12 giây. Đây là giá trị nhỏ nhất, nên ghi 12.

Dữ liệu vào 2

1 1 1 1 1
1
1 1

Dữ liệu ra 2

-1

Ghi chú

Trong ví dụ này, không thể làm cho việc bói thành công, nên ghi -1.