#415. 精灵的问题

精灵在探险的路上遇到了一片森林，现在她需要穿过这片森林。

可以把森林看成一个 $n \times n$ 的网格，入口在点 $(1,1)$ ，出口在 $(n ， n)$ ，森林的每一点都有一个泥泞程度$w_{i,j}$ ，森林中也有 $m$ 个树洞，它们从一点单向地通往另一点。

精灵可以从森林中的一点移动到相邻的距离为$1$的四点内（必须在森林内），也可以穿过树洞从树洞的起点到达树洞的终点，而她每次这么做都会消耗一定的体力：

• 移动到相邻的四点内：到达点的泥泞程度$w$。
• 穿过树洞：对于第$t$次穿过树洞(包括即将穿过的这次)，$k^t$（$k$为一个给定的常数）。

精灵想知道自己穿过森林至少需要多少体力，请你帮帮它。

$k^t$ 指的是: $t$个$k$相乘，即$k$的$t$次幂。

第一行，三个整数 $n,m,k$ ，分别代表森林大小，树洞数目，常数$k$。

第$2$行到第$n+1$行，每行$n$个整数，代表森林中每个点的泥泞程度。

接下来连续的$m$行，每行四个整数$x_1,y_1,x_2,y_2$代表有一个树洞从$(x_1,y_1)$通向$(x_2,y_2)$ 。

一个整数，代表精灵穿过森林至少需要多少体力。

样例输入1：

3 1 5
1 2 3
4 5 6
7 8 9
1 2 3 2

样例输出1：

16

样例输入2：

4 0 7
1 1 4 5
1 4 1 9
1 9 1 8
0 5 2 1

样例输出2：

10

样例解释:
对于样例$1$,从点 $(1,1)$ 走到 $(1,2)$ ，消耗 $2$ 点体力，穿过从 $(1,2)$ 到 $(3,2)$ 的树洞，消耗 $5$ 点体力，最后从 $(3,2)$ 到达 $(3,3)$ ，消耗 $9$ 点体力，共消耗 $2+5+9=16$ 点体力，可以很容易看出，没有比这消耗体力更少的方案了。

对于$100\%$的数据满足: $2\leq n \leq 200$ ， $0\leq m \leq 1000$ ， $5\leq k\leq 10$ ，$0\leq w_{i,j} \leq 1000$ 。

保证点 $(1,1)$ 和 $(n,n)$ 没有树洞（的起点和终点），而且没有任何一点会有一个以上的树洞（的起点和终点）。