In a far away country there is a city facing a big problem. The city is plagued by a deadly gas. Many people have died, but there are groups of survivors at places around the city. Between these places there are roads connecting two distinct places that can still be traversed safely. These roads can be traversed in both directions. It's known the number of days necessary to traverse each road and the two places that it connects. It's also known the number of survivors at each location. Each survivor can get to other places following a sequence of roads.

The mayor will send several helicopters to rescue these people, each having a capacity, a limit on the number of crew (people that it can rescue). Each helicopter will land on a certain day and place.

You should answer an important question for the mayor. How many days are needed to rescue all survivors? If it's not possible to rescue all people you should answer how many of them can be rescued.

Input

The first line of input file have the number of test cases T (T <= 40).

The first line of each test case have N, M, and H, the number of places considered, the number of roads between the places and the number of helicopters that will be sent, respectively. Each place is uniquely identified by a number between 1 and N. The next N lines will have N integers, the i-th line have the number of survivors in place i, Xi. Each of next M lines will have three numbers Aj, Bj and Dj, meaning that there is a way between places Aj and Bj that last Dj days to traverse. The input can contain several roads between the same pair of places. Each of next H lines will have three integers Dh, Ph, and Ch (in this order), meaning that a helicopter with capacity Ch will arrive at place Ph at day Dh. The sum of survivors will not be more than 200. If a survivor can get a helicopter following a sequence of roads, the total time to get the helicopter will not be more than 1000.

Constraints

1 <= N, H <= 50

1 <= M <= 1500

1 <= Aj, Bj, Ph <= N

1 <= Dj, Dh <= 1000

1 <= Ch <= 200

0 <= Xi <= 200

Output

For each test case there is one line in output. If all people can be rescued "All people can be rescued in D day(s) ." should be printed, where D is the minimum number of days to rescue all people. If it is impossible to rescue all people "X survivor(s) can be rescued." should be printed, where X is the maximum number of survivors that can be rescued.

Example

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

Output:
All people can be rescued in 6 day(s).
7 survivor(s) can be rescued.