OK, now you've maximized your level and equipments, it seems there is nothing left to pursue in the game Castlevania. But as a steadfast fan of the series you thought it's not enough yet. Since the game keeps a record of the total time spent in completing the game, you decided to minimize it! In Castlevania, of course, you, as a vampire hunter, are trapped in Dracula's castle. There are N chambers in the castle, and since the castle belongs to Lord Alucard, it is not an ordinary castle: in fact it consists of M castles! Fortunately, you, as the heir of the Belmont family, have inherited the knowledge of teleporting freely between these castles in any chamber. For example, you can teleport in chamber X of Castle A to Castle chamber X of Castle B. But it takes a certain amount of magic power to teleport between castles, and you only have Z magic power in total. When the game starts, you are in Chamber 1 and you are to get to chamber N where Alucard himself resides. You start with Z magic and you have to visit each chamber sequentially (first chamber 1 then 2, then 3...finally N). We assume that you are SO good at the game that you would never be beaten by your enemies. And you can only teleport from a castle to another when you have enough magic power.
Input
The first line of the input is T (T <= 10), the number of test cases, then N blocks followed, each with the following form: The first line contains three integers N (N <= 100), M (M <= 10) and Z (Z <= 100), Then M lines followed each containing N - 1 integers. The ith integer of the jth line is the time need to get from chamber i to chamber i + 1 in castle j. Then followed an M * M integer matrix, the jth integer of the ith line is magic power needed to teleport from castle i to j. The magic power needed to teleport from A to B may not equal to the magic power needed to teleport from B to A.
Output
Print the minimum time needed to get from chamber 1 to chamber N in a single line. You start in Castle 1, but you can end in any castle as long as you are in chamber N. The maximum total time will be within 1000000000.
Sample Input
1
4 2 10
3 4 9
1 2 6
10 10
10 10
Sample Output
9
