IOIOI Cards (Translated)

JOI Spring Training Camp 2014/15
Original Statement / Submission Site

Problem Statement

Chairman K is fond of fortune-telling and often tries various methods. Today, he decides to predict the Japanese team’s performance in the upcoming IOI using special cards: each card has ‘I’ on the front and ‘O’ on the back.

The fortune-telling procedure is as follows:

1. First, select five positive integers A, B, C, D, and E.
2. Arrange A + B + C + D + E cards in a single row. The first A cards are placed face up, followed by B cards face down, then C cards face up, D cards face down, and finally E cards face up. This means the sequence becomes: A ‘I’s, B ‘O’s, C ‘I’s, D ‘O’s, E ‘I’s.
3. Perform one or more (possibly the same operation multiple times) of the N available operations. Operation i (1 ≤ i ≤ N) is defined as: "flip all cards from position Li to Ri (inclusive)". Each card flip takes 1 second, so the operation takes Ri − Li + 1 seconds.
4. After all operations, if all cards are face up (‘I’), the ritual is considered successful.

Chairman K wants to avoid unnecessary card flips. Before the ritual, he wants to know whether success is possible, and if so, the minimum total time required.

Task

Given the card layout and the N operations, determine whether it is possible to make all cards face up. If it is possible, calculate the minimum total time required.

Input

The input consists of:

• The first line: five integers A, B, C, D, and E – the number of cards in each section of Step 2.
• The second line: an integer N – the number of available operations.
• The next N lines: each line contains two integers Li and Ri (1 ≤ Li ≤ Ri ≤ A + B + C + D + E), describing the range for operation i.

Output

Print one line. If the ritual can be completed successfully, output the minimum total time required. Otherwise, print -1.

Constraints

• 1 ≤ A, B, C, D, E ≤ 100,000
• 1 ≤ N ≤ 100,000
• 1 ≤ Li ≤ Ri ≤ A + B + C + D + E

Subtasks

• Subtask 1 [15 points]: N ≤ 10
• Subtask 2 [50 points]: A, B, C, D, E ≤ 50
• Subtask 3 [35 points]: No additional constraints

Sample Input 1

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

Sample Output 1

12

Initial sequence: I O O I I I O O O O I I I I I

Perform operation 2 (flip positions 2–6): I I I O O O O O I I I I I → time = 5 seconds

Then, perform operation 3 (flip positions 4–10): I I I I I I I I I I I I I → time = 7 seconds

Total time = 12 seconds (which is also the minimum).

Sample Input 2

1 1 1 1 1
1
1 1

Sample Output 2

-1

It is not possible to flip all cards to 'I'.