Martian Colony is one of the best single player strategy games developed by a renowned game development company. The player has to destroy several colonies on Mars while playing the game.

The planet Mars has N villages numbered from 1 to N. Among the villages, the village numbered i has di amount of Diamonds. There are E one-way roads between some pair of villages, that is, if there is a road from village u to village v, Martians can only move from village u to village v. A number of villages make a colony when for every pair of villages u and v of that colony, there is a path from village u to the village v and the opposite. A path is a sequence of several roads. Each colony has some hit points which is the sum of the lengths of the roads inside that colony. A colony can be destroyed by using marsa points equal to the hit points of that colony. Destroying a colony will add the total number of diamonds of the villages of that colony to the player’s score.

Alon is your best friend. He loves to play strategy games and trying this new one. He loves to score the maximum always. At some stage of the game he is stuck with M amount of marsa points. He wonders, what is the highest score he can gain using maximum M marsa points. As a best friend of Alon, he seeks your help to calculate the exact score.

Input

The first line of input will contain T denoting the number of test cases. Before every test case there will be a blank line. The first line of the test cases will contain 3 integers N, E and M ( 1 ≤ N ≤ 100, 0 ≤ E ≤ N^2, 1 ≤ M ≤ 5000 ). The next line will contain N integers di ( -100 ≤ di ≤ 100) that represent the number of diamonds in the ith village. Each of the next E lines will contain three integers u, v and w ( 1 ≤ u, v ≤ N, 1 ≤ w ≤ 1000 ) which means there is a road from village u to village v of length w.

Output

For each test case print a single line containing “Case X: S”, where X is the case number and S is the maximum score Alon can score.

Example

Input:
1
3 3 3
3 3 3
1 2 3
2 3 3
2 1 3
Output:
Case 1: 3