IOIOI Cards

Time limit1sMemory limit512 MB

Summary

Given a row of I/O cards and interval flip operations with per-length costs, decide whether all cards can be turned face up and find the minimum total flip time.

Level: Hard8 of 10
Topics: Shortest path, Graph, Math, Prefix sum
Solved: No attempts yet

Problem

Chairman K enjoys fortune telling and practices many forms of it. Today he decided to use cards with 'I' on the front and 'O' on the back to tell the fortunes of the Japanese team at this year's IOI.

The fortune telling works as follows.

First, choose positive integers $A, B, C, D, E$ .
Lay out $A + B + C + D + E$ cards in a single row. The leftmost $A$ cards are face up, the next $B$ cards are face down, the next $C$ cards are face up, the next $D$ cards are face down, and the next $E$ cards are face up. Laid out this way, the row shows $A$ copies of 'I', then $B$ copies of 'O', then $C$ copies of 'I', then $D$ copies of 'O', then $E$ copies of 'I', from left to right.
Choose one or more of the $N$ predetermined operations and perform them in any order. The same operation may be performed more than once. Operation $i$ ( $1 \le i \le N$ ) is "flip every card from the $L_i$ -th to the $R_i$ -th position from the left." Flipping one card takes 1 second, so performing operation $i$ takes $R_i - L_i + 1$ seconds.
If every card is face up after all operations, the fortune telling succeeds.

To avoid flipping cards more than necessary, Chairman K decided to first determine whether the fortune telling can succeed before actually using the cards. Moreover, if it can succeed, he decided to find the minimum time needed to make it succeed.

Given the information about how the cards are laid out and the predetermined operations, write a program that determines whether the fortune telling can succeed and, if so, finds the minimum time needed to make it succeed.

Input

Read the following data from standard input.

The first line contains integers $A, B, C, D, E$ separated by spaces. This means that at the start of the fortune telling, cards are laid out so that the leftmost $A$ are face up, the next $B$ are face down, the next $C$ are face up, the next $D$ are face down, and the next $E$ are face up.
The second line contains the integer $N$ . This means there are $N$ predetermined operations.
Of the following $N$ lines, the $i$ -th line ( $1 \le i \le N$ ) contains integers $L_i, R_i$ separated by spaces. This means that operation $i$ is "flip every card from the $L_i$ -th to the $R_i$ -th position from the left."

Output

If the fortune telling can succeed, print a single line to standard output containing the integer that is the minimum time needed to make it succeed. Otherwise, print $-1$ .

Constraints

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

Examples2

Example 1
Input
```
1 2 3 4 5
3
2 3
2 6
4 10
```
Expected output
```
12
```
Example 2
Input
```
1 1 1 1 1
1
1 1
```
Expected output
```
-1
```