Director K loves fortune-telling and often performs various divinations. Today, he decided to predict the performance of the Japanese team at this year's IOI using cards with 'I' on the front and 'O' on the back.

The method of fortune-telling is as follows:

1. First, decide on positive integers $A, B, C, D, E$.
2. Arrange $A + B + C + D + E$ cards in a single row. At this time, arrange $A$ cards face up, followed by $B$ cards face down, followed by $C$ cards face up, followed by $D$ cards face down, and finally $E$ cards face up. Arranging them in this way results in a sequence of $A$ 'I's, $B$ 'O's, $C$ 'I's, $D$ 'O's, and $E$ 'I's from left to right.
3. Choose one or more operations from $N$ pre-determined types and perform them in any order. You may perform the same type of operation two or more times. The $i$-th type of operation ($1 \le i \le N$) is to "flip all cards from the $L_i$-th card to the $R_i$-th card from the left." Flipping one card takes 1 second. Therefore, performing the $i$-th operation takes $R_i - L_i + 1$ seconds.
4. After the operations are finished, the fortune-telling is successful if all cards are face up.

To avoid flipping cards more than necessary, Director K decided to determine whether it is possible to make the fortune-telling successful before actually using the cards. Furthermore, if it is possible to make the fortune-telling successful, he decided to find the minimum time required to do so.

Task

Given information about the arrangement of the cards and the pre-determined operations, write a program to determine whether it is possible to make the fortune-telling successful, and if so, find the minimum time required to make it successful.

Input

Read the following data from standard input:

• The first line contains integers $A, B, C, D, E$ separated by spaces. This represents that at the beginning of the fortune-telling, $A$ cards are face up, followed by $B$ cards face down, followed by $C$ cards face up, followed by $D$ cards face down, and $E$ cards are face up.
• The second line contains an integer $N$, representing that there are $N$ types of pre-determined operations.
• The $i$-th line of the following $N$ lines ($1 \le i \le N$) contains integers $L_i, R_i$ separated by spaces. This represents that the $i$-th operation is to "flip all cards from the $L_i$-th card to the $R_i$-th card from the left."

Output

If it is possible to make the fortune-telling successful, output the minimum time required to make it successful as an integer on a single line. Otherwise, output -1.

Constraints

All input data satisfies the following conditions:

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

Subtasks

Subtask 1 [15 points]

• $N \le 10$ is satisfied.

Subtask 2 [50 points]

• The following conditions are satisfied:
  • $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$.

Subtask 3 [35 points]

• There are no additional constraints.

Examples

Input 1

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

Output 1

12

Note 1

Initially, the cards are arranged as IOOIIIOOOOIIIII. Performing the 2nd operation results in IIIOOOOOOOIIIII. This operation takes 5 seconds. Subsequently, performing the 3rd operation results in IIIIIIIIIIIIIII, and the fortune-telling is successful. This operation takes 7 seconds. The fortune-telling can be made successful in 12 seconds. Since this is the minimum value, output 12.

Input 2

1 1 1 1 1
1
1 1

Output 2

-1

Note 2

In this input example, the fortune-telling cannot be made successful, so output -1.