#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

Chairman K loves fortune-telling games and is always trying to do some kind of card divination. Today, he is using cards that have 'I' on one side and 'O' on the other to predict this year's IOI team.

The method of divination is as follows:

- First, integers
**A**,**B**,**C**,**D**,**E**are decided. **A**+**B**+**C**+**D**+**E**cards are placed in a row. The first**A**cards are flipped to the 'I' side. The next**B**cards are flipped to the 'O' side. The next**C**cards are flipped to the 'I' side. The next**D**cards are flipped to the 'O' side. The last**E**cards are flipped to the 'I' side. In this manner, going from left to right, there are**A**'I' cards,**B**'O' cards,**C**'I' cards,**D**'O' cards and**E**'I' cards.- There are
**N**types operations, of which 1 or more can be selected. The selected operations can be performed in any order. The same type of operation can even be performed twice or more. Numbering the cards starting from 1 at the left, operation**i**is to flip the**L**_{i}^{th}card to the**R**_{i}^{th}card. Each card takes 1 second to flip, so operation**i**takes**R**-_{i}**L**+ 1 seconds to complete._{i} - After all the operations are completed, if all the cards are facing the 'I' side, the divination is successful.

To avoid flipping more cards than necessary, before actually performing the divination, Chairman K would like to know whether it is possible for the divination to succeed. Furthermore, if it is possible for it to succeed, Chairman K would also like to know the shortest time it would take for the divination to succeed.

Given the information about the cards' initial arrangement and the operations in the divination, write a program that determines if it is possible for the divination to succeed, and if so, the shortest time it would take for the divination to succeed.

### Input

Read from standard input and output

On the first line, there are 5 integers, **A**, **B**, **C**, **D**, **E**. This means that there are **A** 'I' cards, **B** 'O' cards, **C** 'I' cards, **D** 'O' cards and **E** 'I' cards in a row.

On the second line, there is 1 integer, **N**. This means that there are **N** types of operations.

On the **i**^{th} line of the next **N** lines, there are two integers, **L _{i}** and

**R**. This means that operation

_{i}**i**is to flip the

**L**

_{i}^{th}card to the

**R**

_{i}^{th}card in

**R**-

_{i}**L**+ 1 seconds.

_{i}### Output

If it is possible for the divination to succeed, print the shortest time it would take for the divination to succeed on one line. Otherwise, print -1 on one line.

### Constraints

All test cases satisfy these constraints:

- 1 ≤
**A**≤ 100 000. - 1 ≤
**B**≤ 100 000. - 1 ≤
**C**≤ 100 000. - 1 ≤
**D**≤ 100 000. - 1 ≤
**E**≤ 100 000. - 1 ≤
**N**≤ 100 000. - 1 ≤
**L**≤_{i}**R**≤_{i}**A**+**B**+**C**+**D**+**E**(1 ≤**i**≤**N**).

### Subtasks

Subtask 1 (15 points):

**N**≤ 10 is satisfied.

Subtask 2 (50 points):

- 1 ≤
**A**≤ 50. - 1 ≤
**B**≤ 50. - 1 ≤
**C**≤ 50. - 1 ≤
**D**≤ 50. - 1 ≤
**E**≤ 50.

Subtask 3 (35 points):

No further constraints.

### Sample Input 1

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

### Sample Output 1

```
12
```

### Explanation

At first, the row of cards is IOOIIIOOOOIIIII.

After performing operation 2, the row of cards becomes IIIOOOOOOOIIIII. This operation takes 5 seconds.

Subsequently performing operation 3, the row of cards becomes IIIIIIIIIIIIIII. This operation takes 7 seconds.

It is thus possible for the divination to succeed in 12 seconds, so print 12.

### Sample Input 2

```
1 1 1 1 1
1
1 1
```

### Sample Output 2

```
-1
```

### Explanation

In this case, it is impossible for the divination to succeed, so print -1.

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 15 | 15 | 1s | 256MB | Minimum |

2 | 50 | 14 | 1s | 256MB | Minimum |

3 | 35 | 15 | 1s | 256MB | Minimum |

4 | 0 | 2 | 1s | 256MB | Minimum |

### Judge Compile Command

g++ ans.cpp -o ioioi_cards -Wall -static -O2 -lm -m64 -s -w -std=gnu++14 -fmax-errors=512