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

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

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

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

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

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

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

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

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

数据范围:

2<=n,m<=100

1<=W<=5000

1<=k<=15

1<=x<=200

1<=y<=k

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