CF1218C.Jumping Transformers

You, the mighty Blackout, are standing in the upper-left $(0,0)$ corner of $N$x$M$ matrix. You must move either right or down each second.

There are $K$ transformers jumping around the matrix in the following way. Each transformer starts jumping from position $(x,y)$, at time $t$, and jumps to the next position each second. The $x$-axes grows downwards, and $y$-axes grows to the right. The order of jumping positions is defined as ${(x,y),(x+d,y-d),(x+d,y),(x,y+d)}$, and is periodic. Before time $t$ transformer is not in the matrix.

You want to arrive to the bottom-right corner $(N-1,M-1)$, while slaying transformers and losing the least possible amount of energy. When you meet the transformer (or more of them) in the matrix field, you must kill them all, and you lose the sum of the energy amounts required to kill each transformer.

After the transformer is killed, he of course stops jumping, falls into the abyss and leaves the matrix world. Output minimum possible amount of energy wasted.

你，强大的“黑出”（Blackout），正站在一个 $N \times M$ 矩阵的左上角 $(0,0)$ 处。每秒你只能向右或向下移动一格。

矩阵中有 $K$ 个变形金刚（transformer）在不断跳跃，其运动方式如下：每个变形金刚从位置 $(x,y)$ 出发，于时刻 $t$ 开始跳跃，之后每秒跳至下一个位置。其中，$x$ 轴正方向向下，$y$ 轴正方向向右。其跳跃位置序列定义为：

$$\{(x,y),\ (x+d,y-d),\ (x+d,y),\ (x,y+d)\},$$

并以此序列周期性循环。在时刻 $t$ 之前，该变形金刚尚未进入矩阵。

你的目标是抵达矩阵右下角 $(N-1,M-1)$，途中尽可能多地消灭变形金刚，并使消耗的能量总和最小。当你与一个（或多个）变形金刚同时位于矩阵的同一格子时，你必须立即消灭所有这些变形金刚，且将消耗等于这些变形金刚各自击杀所需能量之和的能量值。

一旦某个变形金刚被击杀，它便会立即停止跳跃、坠入深渊，并永远离开矩阵世界。请输出你所能达到的最小总能量消耗。

In the first line, integers $N$,$M$ ($1 \leq N, M \leq 500$), representing size of the matrix, and $K$ ($0 \leq K \leq 5*10^5$) , the number of jumping transformers.

In next $K$ lines, for each transformer, numbers $x$, $y$, $d$ ($d \geq 1$), $t$ ($0 \leq t \leq N+M-2$), and $e$ ($0 \leq e \leq 10^9$), representing starting coordinates of transformer, jumping positions distance in pattern described above, time when transformer starts jumping, and energy required to kill it.

It is guaranteed that all 4 of jumping points of the transformers are within matrix coordinates

第一行包含整数 $N$、$M$（$1 \leq N, M \leq 500$），表示矩阵的尺寸，以及 $K$（$0 \leq K \leq 5 \times 10^5$），表示跳跃型变换器的数量。

接下来 $K$ 行，每行描述一个变换器：数字 $x$、$y$、$d$（$d \geq 1$）、$t$（$0 \leq t \leq N+M-2$）和 $e$（$0 \leq e \leq 10^9$），分别表示该变换器的起始坐标、上述描述的跳跃模式中的跳跃距离、开始跳跃的时间，以及消灭它所需的能量。

保证所有变换器的四个跳跃位置均位于矩阵坐标范围内。

Print single integer, the minimum possible amount of energy wasted, for Blackout to arrive at bottom-right corner.

输出一个整数，表示 Blackout 到达右下角时可能浪费的最少能量。

If Blackout takes the path from (0, 0) to (2, 0), and then from (2, 0) to (2, 2) he will need to kill the first and third transformer for a total energy cost of 9. There exists no path with less energy value.

如果 Blackout 选择从 $(0, 0)$ 到 $(2, 0)$，再从 $(2, 0)$ 到 $(2, 2)$ 的路径，则他需要摧毁第一个和第三个变压器，总能量消耗为 $9$。不存在能量值更小的路径。