题目描述

牛牛注意到家周围的红绿灯排布可以看成一个 $\red{n x m }$的方格图，位置从左上角的 $\red{(1,1)}$到右下角的$\red{(n,m)，}$右上角为$\red{(1,m)}$。地图是上北下南左西右东的。 牛牛计算好了每个路口向下走到下一个路口的时间$\red{d_{i}}$和向右走到下一个路口需 要花费的时间 $\red{e_{i}}$。

在每个路口，向前或向左走只有在绿灯时才可以前进，向右走则可以忽略红绿灯， 通过路口的时间可以忽略不计。某些路口没有加装红绿灯，这些路口可以选择任 意方向前进而不需要等待。

每个路口的红绿灯有自己独立的时间，分别是东西（左右）方向的$\red{a_{i}}$秒绿灯和南 北（上下）方向的$\red{b_{i}}$秒绿灯，东西方向为绿灯时南北方向为红灯，南北方向为绿 灯时同理，初始时所有红绿灯都在南北方向红灯第$\red{0}$秒（如第$\red{i}$个路口，初始之后 是南北方向是$\red{a_{i}}$秒红灯，随后是$\red{b_{i}}$秒绿灯，然后是$\red{a_{i}}$秒红灯，以此类推）。为了简 化问题，设定$\red{t = a_{i} + b_{i}，}$对于所有红绿灯，红灯加绿灯的时间是一样的。如果 $\red{a_{i} = b_{i} = 0，}$则表示该路口未加装红绿灯。

牛牛喜欢欣赏沿途的风景，唯独不喜欢等红绿灯，所以对他来说，等待红绿灯的 时间在他看来时间会流逝缓慢许多。而且，他不会在一条道路的中途停下等时间， 除非是等红绿灯。

他认为的花费代价 $\red{= }$红绿灯等待时间 $\red{\times 10 + }$路途花费时间（不含等红绿灯） 牛牛一开始在位置$\red{(1,1)}$点朝下（南）骑行（等待红绿灯），他希望到达路口 $\red{(x_{e}, y_{e})}$ （任意方向均可），想知道最小花费的代价是多少。

输入格式

第一行输入三个整数$\red{n, m, t，}$表示地图的大小，和红绿灯的总时长$\red{（a_{i} + b_{i}）}$。

第二行输入两个整数$\red{x_{e}, y_{e}，}$表示牛牛要到达的终点。

随后 $\red{n\times m }$行，每行输入四个整数$\red{a_{i}, b_{i}, d_{i}, e_{i}，}$分别为位置$\red{(_{i}/m + 1(}$整除$\red{),i\%m + 1)}$ 的红灯时间、绿灯时间，向下到下一个路口的距离和向右到下一个路口的距离。

对于边缘位置给出的，通向地图之外的$\red{d_{i}, e_{i}}$应该忽略。

对于 $\red{30\%}$的数据，$\red{n, m ≤}$ $\red{3}$。

另有 $\red{10\%}$的数据，$\red{n ≤}$ $\red{1}$或 $\red{m ≤}$ $\red{1}$。

对于总量 $\red{30\%}$的数据，$\red{a_{i}, b_{i} = 0}$。

以上三种数据共占 $\red{60\%}$。

对于 $\red{100\%}$的数据有$\red{1 ≤}$ $\red{n, m ≤}$ $\red{200, 0 ≤}$ $\red{a_{i}, b_{i} ≤}$ $\red{t ≤}$ $\red{60,0 ≤}$ $\red{d_{i}, e_{i} ≤}$ $\red{10^4}$。

数据阶梯型增大。

输出格式

一行输出一个整数，即花费的最小代价。

样例

输入样例

2 3 30
2 3
15 15 15 30
15 15 60 15
0 0 100 0
15 15 0 70
15 15 0 30
20 10 0 0

输出样例

270

提示

样例说明

有几条可选的路线，我们分别来分析一下：

一开始需要在$\red{(1,1)}$等 $\red{15 }$秒的红灯，代价是 $\red{150}$。

路线 $\red{1: (1,1) -> (1,2) }$路程花费时间 $\red{30，}$ $\red{(1,2)->(1,3) ，}$正值东西方向红灯，等 待 $\red{15 }$秒，代价 $\red{150，}$路程花费 $\red{15，}$$\red{(1,3)->(2,3)，}$此时因为是右转，不需要等待 红 绿 灯 （ 而 且 这 里 也 未 加 装 红 绿 灯 ）， 路 程 花 费 $\red{100 ，}$共计代价 $\red{150+30+150+15+100 = 445 }$。

路线 $\red{2: (1,1) -> (1,2) }$路程花费时间 $\red{30，}$ $\red{(1,2)->(2,2) }$右转忽略红绿灯，路程花 费 $\red{60，}$$\red{(2,2)->(2,3)，}$此时时间为 $\red{105，}$正值南北方向绿灯，路程花费 $\red{30，}$共计代 价 $\red{150+30+60+30 = 270 }$。

路线 $\red{3: (1,1) -> (2,1) }$路程花费时间 $\red{15，}$$\red{(2,1)->(2,2)，}$正值南北方向红灯，等待 $\red{15 }$秒，代价 $\red{150，}$路程花费 $\red{70，}$$\red{(2,2)->(2,3) }$正值东西方向红灯，等待 $\red{5 }$秒，代 价 $\red{50，}$路程花费 $\red{30，}$共计代价 $\red{150+15+150+70+50+30=465 }$。

可能还有一些其他路线，如$\red{(1,1)->(2,1)->(2,2)->(1,2)->(1,3)->(2,3)，}$代价更高一 些，综上，最小代价为 $\red{270 }$