Codah ClubGyakorolj. Küldd be. Fejlődj.
Bejelentkezés
Magyar
#00019D

Collecting Golds

Fuad is a gold lover. There are [] golds put in cities (1<=C<=1000) by a rich guy named Sir Wigune. Fuad wants to collect as many golds as possible, after collecting the golds, he needs to go back to his house.


Help Fuad to build his house so that every morning he can collect the maximum number of golds.


Notes: Gold in each city can only be collected once.


InputThe first line of the standard input contains the number 1<=N<=1000 where N corresponds to the number of cities In the next N lines there is one integer Ci, 1<=Ci<=1000, where Ci= number of golds in city i, the next line contains the number M corresponds to number of directed edges (1<=M<=N*N). In the next M lines there are two numbers A and B, means there is a path from A to B.


OutputTo the standard output write one number that is the maximum number of golds Fuad can collect that satisfy the requirements.



Input 1:
[c]4
5
4
1
7
6
1 2
2 3
3 1
2 4
4 2
4 4

Output 1:
17


Input 2:
5
5
4
1
7
9
5
1 2
2 3
3 1
4 5
5 4

Output 2:
16


Input 3:
2
1
100
1
1 2

Output 3:
100


Input 1:
Cities Golds:
 1    5
 2    4
 3    1
 4    7
Fuad can build house everywhere( city numbered 1..4).
There are 6 edges.

Route satisfying the requirement:
*1->2->4->2->3->1 golds:5+4+1+7=17
maximum=17

Input2:
Cities Golds:
 1    5
 2    4
 3    1
 4    7
 5    9
Fuad can build house everywhere( city numbered 1..5).
There are 5 edges.

Route satisfying the requirement:
*1->2->3->1 golds:5+4+1=10
*4->5->4 golds:7+9=16
maximum=16

Input 3:
To get the maximum number of golds, he must build house at town 2 and gets 100 golds.

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.