拉姆少校正在被他的宿敌拉加夫追赶。拉姆必须到达建筑物顶部才能乘坐直升机逃脱。然而,该建筑已着火。拉姆必须选择到达建筑物顶部的最佳路径,以损失最少的生命值。
该建筑由 $$$n$$$ 层组成,每层都有 $$$m$$$ 个房间。让 $$$(i, j)$$$ 代表 $$$i$$$ 层的第 $$$j$$$ 个房间。此外,还安装了 $$$k$$$ 梯子。第 $$$i$$$ 梯子允许 Ram 从 $$$(a_i, b_i)$$$ 移动到 $$$(c_i, d_i)$$$,但不能朝另一个方向移动。如果拉姆使用梯子 $$$i$$$,他还会获得 $$$h_i$$$ 生命值。所有梯子都保证 $$$a_i < c_i$$$。
如果 Ram 在 $$$i$$$ 层,他可以向左或向右移动。然而,跨楼层旅行是危险的。如果 Ram 从 $$$(i, j)$$$ 前往 $$$(i, k)$$$,他会损失 $$$|j-k| \cdot x_i$$$ 健康点。
Ram 在 $$$(1, 1)$$$ 进入大楼,而他的直升机则在 $$$(n, m)$$$ 等待。如果拉姆选择最优路径,他最少损失多少生命值?请注意,这个答案可能是否定的(在这种情况下他会获得健康)。如果拉姆无论走哪条路都无法逃脱拉加夫的魔爪,则输出“NO ESCAPE”。
输入
输入的第一行包含 $$$t$$$ ($$$1 \leq t \leq 5 \cdot 10^4$$$) — 测试用例的数量。
每个测试用例的第一行由 $$$3$$$ 整数 $$$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$$$ 并且建筑物中任意 2 个房间之间最多有一个梯子。
所有测试用例的 $$$n$$$ 总和、$$$m$$$ 总和以及 $$$k$$$ 总和不超过 $$$10^5$$$。
输出
输出 Ram 在从 $$$(1, 1)$$$ 到 $$$(n, m)$$$ 的最优路径上损失的最小生命值。如果 Ram 无论走哪条路都无法逃脱 Raghav 的魔爪,则输出“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)$$$ 的可能路径只有 $$$2$$$:
- 拉姆前往$$$(1, 3)$$$,乘坐梯子前往$$$(3, 3)$$$,前往$$$(3, 2)$$$,乘坐梯子前往$$$(5, 1)$$$,前往$$$(5, 3)$$$,最终乘坐直升机逃离。损失的生命值为 $$$$$$ \begin{align*} &\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{align*} $$$$$$
- 拉姆前往 $$$(1, 3)$$$,乘坐梯子前往 $$$(3, 3)$$$,前往 $$$(3, 1)$$$,乘坐梯子到达 $$$(5, 2)$$$,前往 $$$(5, 3)$$$,最终乘坐直升机逃脱。损失的生命值为 $$$$$$ \begin{align*} &\mathrel{\phantom{=}} x_1 \cdot |1-3| - h_1 + x_3 \cdot |3-1| - h_2 + a_5 \cdot |2-3| \\ &= 5 \cdot 2 - 4 + 8 \cdot 2 - 5 + 4 \cdot 1 \\ &= 21. \end{align*} $$$$$$
在第二个测试用例中,没有指向 $$$(n, m)$$$ 的路径。
在第三种情况下,Ram 前往 $$$(1, 3)$$$ 并使用唯一的梯子到达 $$$(5, 3)$$$。他失去了 $$$5 \cdot 2$$$ 生命值并获得了 $$$h_1 = 100$$$ 生命值。因此,总损失为$$$10-100=-90$$$(负数意味着他在走完这条路后获得了生命值)。