Not Escaping

Description:

Input:

The first line of input contains $$$t$$$ ($$$1 \leq t \leq 5 \cdot 10^4$$$) — the number of test cases.

The first line of each test case consists of $$$3$$$ integers $$$n, m, k$$$ ($$$2 \leq n, m \leq 10^5$$$; $$$1 \leq k \leq 10^5$$$) — the number of floors, the number of rooms on each floor and the number of ladders respectively.

The second line of a test case consists of $$$n$$$ integers $$$x_1, x_2, \dots, x_n$$$ ($$$1 \leq x_i \leq 10^6$$$).

The next $$$k$$$ lines describe the ladders. Ladder $$$i$$$ is denoted by $$$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$$$)  — the rooms it connects and the health points gained from using it.

It is guaranteed $$$a_i < c_i$$$ for all ladders and there is at most one ladder between any 2 rooms in the building.

The sum of $$$n$$$, the sum of $$$m$$$, and the sum of $$$k$$$ over all test cases do not exceed $$$10^5$$$.

Output:

Output the minimum health Ram loses on the optimal path from $$$(1, 1)$$$ to $$$(n, m)$$$. If Ram cannot escape the clutches of Raghav regardless of the path he takes, output "NO ESCAPE" (all uppercase, without quotes).

Sample Input:

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

Sample Output:

16
NO ESCAPE
-90
27

Note:

The figure for the first test case is in the statement. There are only $$$2$$$ possible paths to $$$(n, m)$$$:

• Ram travels to $$$(1, 3)$$$, takes the ladder to $$$(3, 3)$$$, travels to $$$(3, 2)$$$, takes the ladder to $$$(5, 1)$$$, travels to $$$(5, 3)$$$ where he finally escapes via helicopter. The health lost would be $$$$$$ \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*} $$$$$$
• Ram travels to $$$(1, 3)$$$, takes the ladder to $$$(3, 3)$$$, travels to $$$(3, 1)$$$, takes the ladder to $$$(5, 2)$$$, travels to $$$(5, 3)$$$ where he finally escapes via helicopter. The health lost would be $$$$$$ \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*} $$$$$$

Therefore, the minimum health lost would be $$$16$$$.

In the second test case, there is no path to $$$(n, m)$$$.

In the third case case, Ram travels to $$$(1, 3)$$$ and takes the only ladder to $$$(5, 3)$$$. He loses $$$5 \cdot 2$$$ health points and gains $$$h_1 = 100$$$ health points. Therefore the total loss is $$$10-100=-90$$$ (negative implies he gains health after the path).