流水线（wafer）

题目描述

Y 同学正在设计一套半导体自动化生产流水线。该系统包含 $N$ 条平行的传送带，每条传送带上有 $M$ 个加工站。我们将第 $i$ 条传送带的第 $j$ 个加工站记为 $(i, j)$。

在系统运行过程中，存在 $K$ 条特殊的跨带快速通道。第 $i$ 条快速通道允许晶圆从传送带 $a_i$ 的加工站 $b_i$ 直接传输至传送带 $c_i$ 的加工站 $d_i$。由于跨带传输会经过能量补偿器，每通过一次这样的通道，晶圆携带的能量值会增加 $h_i$ 个单位。已知所有快速通道均满足 $a_i < c_i$。

在同一条传送带 $i$ 上，晶圆可以在相邻的加工站之间双向移动。每当晶圆在同带内从站点 $(i, j)$ 移动到站点 $(i, k)$ 时，由于摩擦损耗，能量值会减少 $\vert j - k \vert \times x_i$ 个单位，其中 $x_i$ 为该传送带的单位损耗系数。

晶圆初始位于 $(1, 1)$ 站点，最终需要被送往 $(N, M)$ 站点进行封装。请计算在整个流程中，晶圆能量损耗的最小值（能量损耗 = 总损耗值 - 总增加值）。如果晶圆由于路径断裂无法到达终点，请输出 QAQ。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。

对于每个测试用例： 第一行包含三个整数 $N, M, K$，分别表示传送带数量、每条带上的站点数和快速通道数量。 第二行包含 $N$ 个整数 $x_1, x_2, \dots, x_N$，表示各条传送带的损耗系数。 接下来的 $K$ 行，每行包含五个整数 $a_i, b_i, c_i, d_i, h_i$，描述一个快速通道的起始站点、目标站点和能量增益。

输出格式

对于每个测试用例，输出一行一个整数，表示最小能量损耗。如果无法送达，输出 QAQ。

样例

样例输入 #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
QAQ
-90
27

数据范围与约定

对于 $100\%$ 的数据，保证 $2 \le N, M \le 10^5$，$1 \le K \le 10^5$，$1 \le x_i \le 10^6$，$1 \le h_i \le 10^6$。 所有测试用例的 $\sum N, \sum M, \sum K \le 10^5$。

• 特殊性质 A：保证对于所有通道 $i$，均有 $c_i = a_i + 1$。
• 特殊性质 B：保证所有的 $x_i$ 均相等。