Bajtazar, the vocalist of the heavy metal band Algosia in Antichains, is preparing for a concert in Bajtoszyce. In addition to preparing the favorite songs of the fans gathered in the audience, it is equally important to prepare the sound system.

The sound system consists of $n$ routers and $m$ amplifiers. The microphone is connected to router number 1, and the speaker is connected to router $n$. Each amplifier connects two routers (an input and an output) and has a gain factor $w_i$. Each router also has a maximum throughput $p_i$.

The signal from the microphone has a power of 1. Bajtazar can configure the system to send the signal from the microphone through any sequence of routers connected by amplifiers. The signal power is multiplied by the gain factor of the amplifier after passing through it. If at any point the power of the currently transmitted signal exceeds the throughput of the router it is passing through, that router will burn out, which Bajtazar absolutely wants to avoid.

The signal can pass through the same router or amplifier any number of times. Bajtazar wants to send the signal to the speaker, achieving the maximum possible gain without exceeding the throughput of any of the routers. Help him achieve this.

Input

The first line contains a single integer $T$ ($1 \le T \le 100$) denoting the number of sound systems Bajtazar has. This is followed by $T$ descriptions of the sound systems.

The first line of each description contains two integers $n$ and $m$ ($1 \le n, m$) denoting the number of routers and the number of amplifiers.

The next line contains a sequence of $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le 10^9$), denoting the throughputs of the respective routers.

The next $m$ lines contain descriptions of the amplifiers, where the $i$-th one consists of three integers $a_i$, $b_i$, and $w_i$ ($1 \le a_i, b_i \le n$, $1 \le w_i \le 10^9$) denoting the input router, output router, and the gain factor of the $i$-th amplifier, respectively.

The sum of $n$ over all test cases does not exceed 100, and the sum of $m$ does not exceed 200.

Output

Output $T$ lines; the $i$-th line should contain a single integer denoting the maximum possible signal gain in the $i$-th sound system. If it is not possible to send the signal to the speaker using the $i$-th system, output $-1$ instead.

Examples

Input 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

Output 1

666
1080
4
-1

Note

Explanation of the example: In the first sound system, the optimal configuration sends the signal as follows: $1 \to 1$ (signal with power 2) $\to 2$ (signal with power $2 \cdot 3 = 6$) $\to 1$ (signal with power $6 \cdot 37 = 222$) $\to 2$ (signal with power $222 \cdot 3 = 666$)

In the second system, the optimal solution is: $1 \to 1$ (power 2) $\to 1$ (power $2 \cdot 2 = 4$) $\to 1$ (power $4 \cdot 2 = 8$) $\to 2$ (power $8 \cdot 1 = 8$) $\to 2$ (power $8 \cdot 3 = 24$) $\to 2$ (power $24 \cdot 3 = 72$) $\to 2$ (power $72 \cdot 3 = 216$) $\to 3$ (power $216 \cdot 1 = 216$) $\to 3$ (power $216 \cdot 5 = 1080$)

In the third system: $1 \to 1$ (power 2) $\to 1$ (power $2 \cdot 2 = 4$) $\to 2$ (power $4 \cdot 1 = 4$)

In the fourth system, sending the signal through the amplifier would result in a signal with power $1\,000\,000\,000$, exceeding the throughput of router number 2. Thus, transmitting a signal of any power is not possible.