2765.D - 漂流竞速

## 题目描述

计算鸭要去参加一个橡皮艇河道漂流比赛，比赛的场地可以视为一个$n*m$的网格图，网格图的每一个位置都是河道的交错口。比赛的起点在$(1,1)$，也就是整个网格图的左上角，比赛的目标是尽快到达插着终点旗帜的$(x_{e},y_{e})$。网格图的右上角坐标为$(1,m)$，右下角坐标为$(n,m)$。从高空看，网格图的方位是符合上北下南，左西右东的。

由于不同的位置，水流的情况不同，所以控制橡皮艇划行的用时也不同。幸好，计算鸭通过研究天气预报，已经得知从每个河道交错口，划行到右侧河道口的用时$e_{i}$和划行到下侧河道口的用时$d_{i}$。

为了增加比赛难度，主办方在一些位置设置了漩涡制造器，可以在这个位置制造漩涡，来交替干扰南北方向或者东西方向的划行。如果在漩涡出现期间，强行沿着被干扰的方向划行就会导致翻船，失去比赛资格。每个干扰器有自己的运行规律，首先会通过制造漩涡，干扰南北方向的划行$a_{i}$秒，然后干扰东西方向的划行$b_{i}$秒，两种干扰模式无缝交替运行。由于主办方只采购了一款漩涡制造器，所以$a_{i}+b_{i}=t$，是一个恒定的数值。在通过一些河道交错口时，选手不得不选择等待漩涡制造器切换模式，来避免翻船。当然，有一些位置主办方是没有放置漩涡制造器的，选手们可以随意划行，不用担心翻船。

此外，为了给比赛增加一些策略性，主办方将选手的比赛用时定义为：等待漩涡制造器的时间乘以$10$，加上划行用时。

现在，计算鸭想知道，他到达终点时的最小比赛用时是多少。

## 注意

- 计算鸭一开始的位置在$(1,1)$，并且是面朝南的。
- 当计算鸭想要通过向右划行进入下一个河道口，是不受任何干扰器的干扰的。
- 如果计算鸭当前面朝南，那么他可以左拐或者直行，如果当前南北方向没有漩涡制造器的干扰，那么准许通行，反之不行。
- 如果计算鸭当前面向东，那么他可以直行或者右转，右转是可以忽略干扰的，但是直行不行，如果当前东西方向没有漩涡制造器的干扰，那么准许直行，反之不行。

## 输入格式

第一行输入三个整数$n, m, t$，表示比赛场地的大小，和漩涡制造器的工作周期时长$t$。

第二行两个整数$x_{e},y_{e}$，表示终点坐标。

接下来$n*m$行，每行四个整数$a_{i},b_{i},d_{i},e_{i}$，含义如题面所述，为每个河道交错口的信息。给出的信息顺序为从左到右，从上到下的河道交错口顺序。如果$a_{i}+b_{i}=0$，就表示这个位置没有被主办方放置漩涡制造器。

比赛过程中不允许移动到比赛场地之外。

在$0$时刻，也就是比赛开始时，所有的干扰器会首先开始干扰南北方向的划行，然后是东西方向，依次交替。

对于$30\%$的数据，$n, m \le 3$。

另有$10\%$的数据，$n \le 1$或 $m \le 1$。

对于另外$ 30\%$的数据，$a_i, b_i = 0$

对于$ 100\%$的数据有$1 \le n, m \le 200$

$0 \le a_i, b_i \le t \le 60$

$0 \le d_i, e_i \le 10^4$。

## 输出格式

输出一个整数，表示答案。

## 输入
```in1
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
```

## 输出
```out1
270
```

## 提示