201. [BYVoid S1] 埃雷萨拉斯的宝藏

【问题描述】

一万两千年前，精灵还是在艾萨拉女王的统治下，辛德拉是女王手 下一名很有地位的法师。他受任建造了一座城市，来保存女王的法师们进行魔法研究的成果和法术物品。这个城市就是埃雷萨拉斯。永恒之井的爆炸，使这里的精灵 和总部联系中断，并失去了永恒之井的水做为能量的来源。辛德拉的后人为了满足魔法的欲望，捕猎了一个恶魔，伊莫塔尔，并以水晶塔建造了一个带有能量平衡系 统的结界监狱，水晶塔从恶魔身上吸取能量，一部分维持结界监狱，一部分可以让精灵狂热者吸收。近万年平安无事。但是现在，恶魔的能量被消耗得越来越多，最 终变得不稳定，已经难以维持结界监狱的消耗。统治这里的托尔塞林王子开始下令屠杀。只有少数狂热者之外的其他人都要死，以减少魔法能量的消耗。

终于，强大的戈多克食人魔入侵了埃雷萨拉斯，并杀死了大量的精灵。他们把这里当作他们的领地，叫做厄运之槌。面临灭顶之灾的精灵们把他们祖先留下的宝藏用魔法结界藏了起来，以防戈多克食人魔抢走。

作为一名勇敢的探险者，你悄悄来到了埃雷萨拉斯，来寻找传说中的宝藏。终于，你看到了宝藏，他就在你的前方不远处。但是你不能贸然前进，因为路上有着强大的魔法结界。这些结界根据能量的不同分为P种，踏入每种结界，你都会受到一定的伤害。为了拿到宝藏，这些伤害算不了什么。但是你要尽可能地减少伤害，请你设计一条路线，使你穿越结界获取宝藏受到的伤害最少。

下面是一个魔法结界能量示意图，结界是一个正方形，内部有P种不同的能量，每种字母表示一种能量。你从最上端开始走，每次能走到与你所在的位置邻接的一个单元格，或者在同种能量结界中任意传送。重复进入同一种能量结界不会再次受到伤害。

|AAABBC|
|ABCCCC|
|AABBDD|
|EEEEEF|
|EGGEFF|
|GGFFFF|

你有H点生命值，请你在贸然行动之前先判断是否能够活着（生命值大于0）穿越结界拿到宝藏，如果能够，请求出最大的生命值。

【输入格式】

第1行 三个非负整数 N P H。N为结界的边长，P为不同的能量结界的数量，H为你的生命值。

第2-P+1行 每行一个非负整数，表示走到该种能量结界受到的伤害值。

第P+2至第P+2+N行 每行N个正整数，为地图上该单元格的能量种类的编号，编号为1..P。

【输出格式】

如果你能够穿越结界到达对岸的宝藏，输出最多剩余的生命值。如果不能穿越，输出NO。

【样例输入】

6 7 10
3
1
2
2
1
1
3
1 1 1 2 2 3
1 2 3 3 3 3
1 1 2 2 4 4
5 5 5 5 5 6
5 7 7 5 6 6
7 7 6 6 6 6

【样例输出】

7

【样例说明】

路线为：起始-2-5-6-目标

1 1 1 2 2 3
1 2 3 3 3 3
1 1 2 2 4 4
5 5 5 5 5 6
5 7 7 5 6 6
7 7 6 6 6 6

【数据规模】

对于40%数据，4<=N<=10；

对于100%数据，4<=N<=50，1<=P<=N*N，0<=H<=200000000。