逃离火楼

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

Ram 少校正被他的死敌 Raghav 追赶。Ram 必须到达大楼的顶层，才能乘直升机逃脱。然而，大楼正在燃烧。Ram 必须选择一条最优路径，以损失最少的生命值到达大楼顶层。

大楼共有 $n$ 层，每层有 $m$ 个房间。用 $(i, j)$ 表示第 $i$ 层的第 $j$ 个房间。此外，大楼中安装了 $k$ 个梯子。第 $i$ 个梯子允许 Ram 从 $(a_i, b_i)$ 到 $(c_i, d_i)$，但不能反向使用。Ram 使用第 $i$ 个梯子时会获得 $h_i$ 点生命值。保证所有梯子都有 $a_i < c_i$。

如果 Ram 在第 $i$ 层，他可以向左或向右移动。在同一层内，从 $(i, j)$ 移动到 $(i, k)$，会损失 $|j-k| \cdot x_i$ 点生命值。

Ram 从 $(1, 1)$ 进入大楼，直升机停在 $(n, m)$ 等待他。请问 Ram 选择最优路径后，最少会损失多少生命值？注意，答案可能为负数（即他获得了生命值）。如果无论如何都无法逃脱，请输出 "NO ESCAPE"。

输入格式

输入的第一行包含一个整数 $t$（$1 \leq t \leq 5 \cdot 10^4$），表示测试用例的数量。

每个测试用例的第一行包含三个整数 $n, m, k$（$2 \leq n, m \leq 10^5$；$1 \leq k \leq 10^5$），分别表示楼层数、每层房间数和梯子的数量。

每个测试用例的第二行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$（$1 \leq x_i \leq 10^6$）。

接下来的 $k$ 行描述每个梯子。第 $i$ 个梯子用 $a_i, b_i, c_i, d_i, h_i$ 表示（$1 \leq a_i < c_i \leq n$；$1 \leq b_i, d_i \leq m$；$1 \leq h_i \leq 10^6$），表示梯子连接的房间和使用该梯子获得的生命值。

保证所有梯子都有 $a_i < c_i$，且任意两房间之间至多有一条梯子。

所有测试用例中 $n$、$m$、$k$ 的总和均不超过 $10^5$。

输出格式

对于每个测试用例，输出从 $(1, 1)$ 到 $(n, m)$ 的最小生命值损失。如果无论如何都无法逃脱，请输出 "NO ESCAPE"（全部大写，不带引号）。

样例输入 1

4
5 3 3
5 17 8 1 4
1 3 3 3 4
3 1 5 2 5
3 2 5 1 6
6 3 3
5 17 8 1 4 2
1 3 3 3 4
3 1 5 2 5
3 2 5 1 6
5 3 1
5 17 8 1 4
1 3 5 3 100
5 5 5
3 2 3 7 5
3 5 4 2 1
2 2 5 4 5
4 4 5 2 3
1 2 4 2 2
3 3 5 2 4

样例输出 1

16
NO ESCAPE
-90
27

提示

第一个测试用例的图见题面。到 $(n, m)$ 只有两条可能的路径：

• Ram 先到 $(1, 3)$，使用梯子到 $(3, 3)$，再到 $(3, 2)$，使用梯子到 $(5, 1)$，最后到 $(5, 3)$ 乘直升机逃脱。生命值损失为

$$\begin{aligned} &\mathrel{\phantom{=}} x_1 \cdot |1-3| - h_1 + x_3 \cdot |3-2| - h_3 + x_5 \cdot |1-3| \\ &= 5 \cdot 2 - 4 + 8 \cdot 1 - 6 + 4 \cdot 2 \\ &= 16。 \end{aligned}$$

• Ram 先到 $(1, 3)$，使用梯子到 $(3, 3)$，再到 $(3, 1)$，使用梯子到 $(5, 2)$，最后到 $(5, 3)$ 乘直升机逃脱。生命值损失为

$$\begin{aligned} &\mathrel{\phantom{=}} x_1 \cdot |1-3| - h_1 + x_3 \cdot |3-1| - h_2 + x_5 \cdot |2-3| \\ &= 5 \cdot 2 - 4 + 8 \cdot 2 - 5 + 4 \cdot 1 \\ &= 21。 \end{aligned}$$

因此，最小生命值损失为 $16$。

第二个测试用例中，没有路径可以到达 $(n, m)$。

第三个测试用例中，Ram 先到 $(1, 3)$，使用唯一的梯子到 $(5, 3)$。他损失 $5 \cdot 2$ 生命值，获得 $h_1 = 100$ 生命值。因此总损失为 $10-100=-90$（负数表示他获得了生命值）。

数据范围

子任务编号	分值	特殊限制
1	20	$n,m\le 30$，$k\le 80$
2	40	$k\le 1500$
3		无特殊限制