CF1218C Jumping Transformers

你，强大的 Blackout，正站在 $N \times M$ 矩阵的左上角 $(0,0)$。你每秒必须向右或向下移动一格。 矩阵中有 $K$ 个变形金刚在跳跃。每个变形金刚从位置 $(x, y)$、在时间 $t$ 开始跳跃，每秒跳到下一个位置。$x$ 轴向下增长，$y$ 轴向右增长。跳跃的顺序为 $ \{(x, y), (x+d, y-d), (x+d, y), (x, y+d)\} $，并且循环往复。在时间 $t$ 之前，变形金刚不会出现在矩阵中。 你需要到达右下角 $(N-1, M-1)$，途中如果遇到变形金刚（可能有多个），你必须全部击杀，并损失击杀每个变形金刚所需的能量之和。 被击杀的变形金刚会立刻消失，不再跳跃。请输出 Blackout 到达右下角所需消耗的最小能量。

第一行包含整数 $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$），分别表示变形金刚的起始坐标、跳跃模式中每步的距离、开始跳跃的时间，以及击杀该变形金刚所需的能量。 保证每个变形金刚的 4 个跳跃点都在矩阵范围内。

输出一个整数，表示 Blackout 到达右下角所需消耗的最小能量。

如果 Blackout 选择从 $(0, 0)$ 走到 $(2, 0)$，再从 $(2, 0)$ 走到 $(2, 2)$，他需要击杀第一个和第三个变形金刚，总能量消耗为 9。不存在能量消耗更少的路径。 由 ChatGPT 4.1 翻译