Background

A storm has swept through Mitakihara City.

Before the municipal meteorological bureau could establish any monitoring facilities, the only way to determine the state of the storm was to rely on data from anemometers located throughout the city. This task has been assigned to you—a newly hired data engineer at the meteorological bureau.

Description

There are $M$ main streets in the city, connecting $N$ intersections. Each intersection has an anemometer, where the reading at intersection $i$ is $v_i$; a higher reading indicates stronger wind force.

A "venturi effect" may occur in the streets, where airflow through a narrow area leads to decreased pressure and increased velocity. This causes the wind speed through the street to increase, making the anemometer readings at the intersections connected by that street appear higher than their true values. The intensity of this effect for the $i$-th street is $e_i$.

To determine the extent of the storm's center, you need to find a set $S$ consisting of at most $K$ streets (it can be $0$ streets; note that you cannot select the same street multiple times) to maximize: $$ \sum\limits_{x\in I(S)} v_x -\sum\limits_{y\in S} e_y \tag{1} $$ where $I(S)$ denotes the set of all intersections connected to at least one street in $S$.

If an intersection is connected to more than one street in $S$, it is still counted only once. Meteorological experts suspect that there may be multiple smaller cyclones on the periphery of the storm, potentially leading to multiple independent storm centers; therefore, the set of streets you select does not necessarily have to be connected.

Please complete the task as soon as possible; the meteorological bureau's ability to take further action depends on your performance.

Input

The first line contains a positive integer $T$, representing the number of test cases. For each test case:

• The first line contains three positive integers $N, M, K$, representing the number of intersections, the number of streets, and the upper limit on the number of streets to select, respectively. Intersections are labeled from $1$ to $N$, and streets are labeled from $1$ to $M$.
• The second line contains $N$ non-negative integers, representing $v_1, v_2, \dots, v_N$.
• The next $M$ lines each contain three integers $a_i, b_i, e_i$, indicating that street $i$ connects intersections $a_i$ and $b_i$, with a venturi effect intensity of $e_i$.

Output

For each test case, output a single integer representing the maximum value of expression $(1)$.

Examples

Input 1

1
5 5 2
1 2 4 8 16
1 2 1
1 3 2
3 4 2
4 5 2
2 5 1

Output 1

27

Note 1

The set $S$ should contain street $(2,5)$ and street $(3,4)$, with a sum of $e_i$ values equal to $3$. At this point, $I(S)$ contains nodes $2, 3, 4, 5$, with a sum of $v_i$ values equal to $30$.

Subtasks

For all data:

• $\sum 2^K(N+M)\leq 10^6$, where the summation is over all test cases in a single input.
• $1\leq T\leq 5$
• $1\leq N, M, K$
• $0\leq e_i, v_i\leq 10^8$
• $1\leq a_i, b_i\leq N$
• The undirected graph formed by all intersections and streets has no self-loops, but may contain multiple edges, may be disconnected, and may contain isolated vertices.
• The answer is guaranteed not to exceed $2\cdot 10^9$.

Subtask 1: 30 points, $\sum (N+M)\leq 1500$

Subtask 2: 30 points, $K\leq 9$

Subtask 3: 40 points, no additional restrictions