Zen gardens are intended to serve as an intimate imitation of nature as to aid in meditation about the true meaning of life. Therefore, Blake has decided to spend her summer building one in her backyard.

Each flower has a harmony value, and so she's planted flowers **in a row** as to ensure a peaceful garden. However, she's discovered that pairs of flowers, when planted beside each other, cause a **decrease** in the overall harmony of the garden.

The total harmony value of a Zen garden is given by the sum of all flower **harmony** values minus the sum of all **disturbance** values. As she wants her garden to have the **maximum** harmony, she can remove flowers as to eliminate the disturbance they cause.

What is the maximum overall harmony value that Blake can hope to get out of her garden?

#### Input Specification

The first line of input will consist of the single integer .

The second line will consist of space-separated integers representing the meditation values (between and ) of flowers to as they are planted in Blake's garden.

The next line will consist of the single integer .

The next lines will each consist of two space-separated integers, and , , representing that flower and together cause a decrease in the overall harmony by . Removing either or will remove the disturbance .

It is guaranteed that all flowers will **at most** be part of **one** pair.

#### Output Specification

Output the maximum possible overall meditation value of the garden.

#### Sample Input

```
4
5 10 15 20
2
1 30
3 4
```

#### Sample Output

`41`

#### Explanation for Sample Output

After removing the first flower, the sum of the first two flowers is , as the garden no longer incurs the penalty of . For flowers and , the best choice is to leave them alone, as the penalty of is negligible. Adding these, we obtain the desired output.

## Comments