
73  ZOJ Monthly, December 2008  F
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 Author: LIN, Yue Source: ZOJ Monthly, December 2008 