提示: 欢迎访问OurACM平台。
Problem 1514 A Tour in Loquat Orchard

Accept: 122    Submit: 288
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

The price of tzw’s loquat is cheaper and cheaper these years. For this reason, he introduced a home marketing strategy- A Tour in Loquat Orchard. In tzw’s orchard, there are several loquat trees and each tree has a certain number of loquats. He labeled each tree with the number of 1, 2... n. For example, there are 10 loquat trees, and the number of loquats on each loquat tree are: 8, 14, 2, 17, 33, 26, 15, 17, 19, 6. Meanwhile, he gives out the relationships between trees, is showed as follows:

These relationships show that after tourist picked out one tree, he/she can pick the other tree subsequently; but if there are more than one subsequent trees he/she can only choose one of them .And if there is none subsequent tree, then the picking loquats activity ended.

After paying the visiting fee to tzw, the tourist can begin his/her picking loquat from any loquat tree. For the sample above, we can follow the order of 5->6->7->8->10, and then we can get 33+26+15+17+6=97 loquats. And in this way, tourist can get the largest number of loquats.

★ In order to let tourist picking fewer loquats. for each tree, tzw gives out very small number of subsequent trees, even empty. -_-

Input

There are multiple test cases. The first line of each test case contains a positive integer n. (1≤n≤100 000). Indicating that there are n loquat trees in the orchard. The second line contains n integers, representing number of loquats on each loquat tree., The third line contains a positive integer m. (1≤m≤200 000). indicating there are m relationships between these loquat trees. In the following m lines, each line contains two numbers b and e, indicting the tourist after picking loquats on the tree b ,he/she can picking loquats on the tree e(1≤b<e≤n).

Output

For each test case, print a line containing the maximum number of loquats that tourist can pick.

Sample Input

10 8 14 2 17 33 26 15 17 19 6 9 1 3 1 4 2 3 2 7 3 6 5 6 6 7 7 8 8 10

Sample Output

97

Source

FZU 2007 ICPC Qualification Round I

Submit  Back  Status  Discuss