#2869. 上街

上街

题目描述

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

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

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

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

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

输入格式

第一行输入三个整数n,m,t\red{n, m, t,}表示地图的大小,和红绿灯的总时长ai+bi\red{(a_{i} + b_{i})}

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

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

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

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

另有 10%\red{10\%}的数据,n\red{n ≤} 1\red{1}m\red{m ≤} 1\red{1}

对于总量 30%\red{30\%}的数据,ai,bi=0\red{a_{i}, b_{i} = 0}

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

对于 100%\red{100\%}的数据有1\red{1 ≤} n,m\red{n, m ≤} 200,0\red{200, 0 ≤} ai,bi\red{a_{i}, b_{i} ≤} t\red{t ≤} 60,0\red{60,0 ≤} di,ei\red{d_{i}, e_{i} ≤} 104\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

提示

样例说明

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

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

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

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

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

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