Jumping Transformers

题意翻译

- 你要从 $(0,0)$ 向右或向下走到 $(N - 1, M - 1)$ - 图上有 $K$ 个障碍，在 $t_i$ 时刻，$(x_i,y_i)$ 会出现一个障碍，并且接下来的每秒会按照 $(x+d,y-d),(x+d,y),(x,y+d),(x,y)$ 的方式周期性移动（保证不会跳出边界）。恰好碰到这个障碍时，你可以花费 $e_i$ 将它移除（以后都不出现） - 问从起点到终点最小花费 - $1 \le N,M \le 500$，$0 \le K \le 5 \times 10^5$，$d_i \ge 1$，$0 \le t \le N+M-2$

题目描述

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.

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例 #1

3 3 5
0 1 1 0 7
1 1 1 0 10
1 1 1 1 2
1 1 1 2 2
0 1 1 2 3

输出样例 #1

9

说明

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.