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 ~N~ flowers in a row as to ensure a peaceful garden. However, she's discovered that ~M~ 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 ~N~ ~(4 \le N \le 100\,000)~.

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

The next line will consist of the single integer ~M~ ~(1 \le M \le \dfrac{N}{2})~.

The next ~M~ lines will each consist of two space-separated integers, ~a~ ~(1 \le a < N)~ and ~d~ ~(1 \le d \le 1\,000)~, representing that flower ~a~ and ~a+1~ together cause a decrease in the overall harmony by ~d~. Removing either ~a~ or ~a+1~ will remove the disturbance ~d~.

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 ~10~, as the garden no longer incurs the penalty of ~30~. For flowers ~3~ and ~4~, the best choice is to leave them alone, as the penalty of ~4~ is negligible. Adding these, we obtain the desired output.