DMPG '15 S3 - Zen Garden

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

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

5 10 15 20
1 30
3 4

Sample Output


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.


There are no comments at the moment.