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.