问题 I: 勇士之力

问题 I: 勇士之力

时间限制: 1 Sec  内存限制: 128 MB
提交: 303  解决: 61
[状态] [讨论版] [提交] [命题人:]
题目描述

勇士一斗为了拯救九条裟罗,他必须要穿越一片迷宫。一斗每次只能向东或者向南走,不能向西或者向北走。这个迷宫的入口位于西北角,而迷宫的出口位于东南角。

迷宫的每个道路交叉点都存在一个丘丘人,丘丘人的种类不同,他们的攻击力也不同。丘丘人的种类有很多种,列如可能会有木盾丘丘人,冰盾丘丘人,爆弹丘丘人,雷弹丘丘人,射手丘丘人,冰箭丘丘人,风丘丘萨满,草丘丘萨满,和一斗最讨厌的冰丘丘萨满等等多种丘丘人。我们会给出每种丘丘人的攻击力,并且用数字来代表位于迷宫道路交叉点的丘丘人是什么种类。

一斗有一个初始血量W,他每经过一个道路交叉点就会与位于哪里的丘丘人交战,虽然一斗有着斗战岩牛,但还是要不可避免的扣除一次丘丘人的攻击力大小的血量。请问一斗是否能在血量大于0的情况下在迷宫的出口处遇到九条裟罗,如果可以的话就输出剩余的最大血量,否则输出-1

注意:起点西北角和出口东南角不存在丘丘人,也就是说值为0

输入

第一行是两个整数n,m分别代表迷宫的行数和列数。

第二行是一斗的初始血量W

第三行是丘丘人的种类数量k

第四行是k个丘丘人的攻击力x,以空格隔开。注意我们认为丘丘人的种类编号是1~k0默认为没有丘丘人。

接下来是n行数据每行数据有m个数,从左向右顺序描述了每个道路交叉点的丘丘人种类y

数据范围:

2<=n,m<=100

1<=W<=5000

1<=k<=15

1<=x<=200

1<=y<=k


输出

输出一斗到达迷宫出口时剩余的最大血量,如果小于等于0则输出-1.

样例输入 Copy
3 3
10
3
2 1 3
0 3 3
2 2 3
2 1 0
样例输出 Copy
6