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?
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 the maximum possible overall meditation value of the garden.
4 5 10 15 20 2 1 30 3 4
Explanation of Sample Input
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.