You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

PA 2025 R5B.

题目描述

扩音系统由 $n$ 个路由器和 $m$ 个放大器组成。麦克风连接到第 $1$ 号路由器，扬声器连接到第 $n$ 号路由器。

每个放大器连接两个路由器（输入和输出），增益系数为 $w_i$。路由器的最大带宽为 $p_i$。

麦克风的信号功率为 $1$。配置系统，使信号在放大器、路由器中传输。信号经过放大器后，功率会乘以该放大器的增益系数，但是为了避免烧毁，通过路由器的信号功率必须不大于 $p_i$。

信号可以多次通过同一路由器或放大器。最终将信号传输到扬声器（到达 $n$ 号路由器），在路由器不烧毁的前提下，最大化信号的功率。求出可能的最大功率。

输入格式

本题单个测试点内含有多组测试数据。

第一行，正整数 $T$，表示测试数据组数。接下来依次描述 $T$ 组数据：

每组数据第一行，两个正整数 $n,m$。

每组数据第二行，$n$ 个正整数 $p_1,p_2,\ldots,p_n$。

每组数据接下来的 $m$ 行，每行三个正整数 $a_i,b_i,w_i$，表示放大器的输入路由器、输出路由器和增益系数。

输出格式

输出 $T$ 行，每行一个整数：

• 若能成功将信号传输到扬声器，输出可能的最大增益系数；
• 否则，输出一行一个 $-1$。

4
2 3
250 1000
1 1 2
1 2 3
2 1 37
3 5
500 800 1100
1 1 2
1 2 1
2 2 3
2 3 1
3 3 5
2 2
4 4
1 1 2
1 2 1
2 1
10 10
1 2 1000000000

666
1080
4
-1

提示

样例解释

$114(514)$ 表示，信号到达第 $114$ 个路由器时，功率为 $514$。

• 样例 $1$ 解释：

最优路径：$1(1)\to 1(1\times 2)\to 2(2\times 3)\to 1(6\times 37)\to 2(222\times 3)$。

• 样例 $2$ 解释：

最优路径：$1(1)\to 1(2)\to 1(4)\to 1(8)\to 2(8)\to 2(24)\to 2(72)\to 2(216)\to 3(216)\to 3(1080)$。

• 样例 $3$ 解释：

最优路径：$1\to 1(2)\to 1(4)\to 2(4)$。

• 样例 $4$ 解释：路由器 $2$ 一定会被烧毁，所以无法传到路由器 $2$。

数据范围

• $1\le n,\sum n\le 100$；
• $1\le m,\sum m\le 200$；
• $1\le p_i\le 10^9$；
• $1\le a_i,b_i\le n$；
• $1\le w_i\le 10^9$。