ZOJ Problem Set - 3017
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.
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.
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.
1 4 2 10 3 4 9 1 2 6 10 10 10 10
Author: SONG, Yu
Source: ZOJ Monthly, August 2008