B. 旅行

给定一个N*N大小的二维数组，该二维数组使用P种不同数字进行填充。如下图所示，你需要从该二维数组的第一行移动到最后一行，你的移动方向只能是上下左右。在该二维数组中，同一个数字所标识的区域为一类区域，你需要注意的是：

（1）当你进入不同的区域时，你需要消耗一定的体力，进入不同的区域所消耗的体力不同；

（2）你可以在同一类区域内任意传送；

（3）重复进入同一类区域不消耗任何体力。

你一共有H点体力值，请你计算一下从第一行移动到最后一行最多能剩下多少体力。

输入数据有若干行。

第一行为三个非负整数N、P、H。N表示矩阵的大小为N*N，P代表矩阵中一共有P种不同的数字，H为你的体力。

第二行到P+1行，每行一个非负整数，表示进入该区域所需要消耗的体力值。

第P+2至第P+2+N行，每行N个正整数，表示矩阵中所填充的数字。

输出数据为一行一个整数，表示你从第一行移动到最后一行最多能剩下多少体力。

注意，本题的所有测试数据都保证你最终所剩下的体力为正数。

【样例说明】

选择的路线如下：2—5—6。

第一步，初始进入(1, 4)单元格，消耗1点体力；

第二步，从(1, 4)传送到(3, 3)，不消耗体力；

第三步，从(3, 3)进入(4, 3)，消耗1点体力；

第四步，从(4, 3)传送到(5, 4)，不消耗体力；

第五步，最终从(5, 4)进入(6, 4)抵达终点，消耗1点体力；

总共消耗3点体力，最多还剩下7点体力。

【数据规模与约定】

对于50%的数据，4≤N≤10、1≤P≤N*N、0≤H≤2*10^8

对于100%的数据，4≤N≤50、1≤P≤N*N、0≤H≤2*10^8