Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
73 - ZOJ Monthly, December 2008 - F
Greedy

Time Limit: 1 Second      Memory Limit: 32768 KB

watashi's mm is so pretty, as well as greedy. She attends the treasure hunt game. There are some treasures in each cities. She should start from the city 1 and go from one city to another city iff there exists a directed road between them. When she arrives at one city for the first time, she can get all the treasures in the city. Furthermore, when she arrives at the last city N, she will be sent back to the city 1 at once. The game has a special rule, the participant can play only Q times. For her greedy, she turns to watashi for help. She wants to get as many treasures as possible.

Input

The first line of each ase is a integer N (1 <= N <= 1000), representing the total number of cities.

The following N integers, the ith integer represents the number of treasures in the ith city, it won't exceed 1000.

The next line is an interger M, represents the number of roads.

The following M lines, the ith line contains two integers "X Y", represents there exists a road from X to Y.

The last line contains a number 0 <= Q <= 10.

You can assume that if you can reach from city A to B, you can't reach from B to A.

Output

For each case, output the corresponding answer.

Sample Input

5
1 2 30 4 5
5
1 2
2 4
4 5
1 3
3 5
1
5
1 2 30 4 5
5
1 2
2 4
4 5
1 3
3 5
2
5
1 2 30 4 5
5
1 2
2 4
4 5
1 3
3 5
3

Sample Output

36
42
42

Hint

If Q = 1, the route is 1 - 3 - 5
If Q = 2, the route is 1 - 3 - 5; 1 - 2 - 4 - 5
If Q = 3, the route is 1 - 3 - 5; 1 - 2 - 4 - 5; the last route make no sense for all the treasures are got.


Author: LIN, Yue
Source: ZOJ Monthly, December 2008
Submit    Status