Problem Statement

You are a strategy consultant at a huge corporation.
You now have to decide, for each of $N$ cities, whether to launch a new business there.
The plan consists of the following elements.

• Individual businesses:
  Running a business on its own in city $i$ yields a net profit (or net loss) of $P_i$.
  $P_i$ may be negative.
• Production flows (dependencies):
  There are $M$ production flows $U\rightarrow V$.
  Each one means that "the business in city $V$ uses the products of city $U$ as raw materials".
  Therefore, in order to run a business in city $V$, you must also run a business in city $U$.
  These dependencies may form cycles.
• Business partnerships (synergies):
  There are $K$ kinds of "business partnership" opportunities.
  The $j$-th partnership concerns the pair of cities $(A_j, B_j)$, and an additional synergy profit of $S_j$ arises only if businesses are run in both cities.

You choose in which cities to run businesses, aiming to maximize the total profit.
The total profit is calculated as " $($ the sum of $P_i$ of the chosen businesses $)+($ the sum of $S_j$ of the business partnerships whose conditions are satisfied $)$ ".
Find the maximum achievable total profit.

Input

$N$
$P_1\ P_2\ \dots\ P_N$
$M$
$U_1\ V_1$
$\dots$
$U_M\ V_M$
$K$
$A_1\ B_1\ S_1$
$\dots$
$A_K\ B_K\ S_K$

• $1\leq N\leq 200$
• $0\leq M,K\leq 200$
• $-10^9\leq P_i\leq 10^9\ (1\leq i\leq N)$
• $1\leq U_i,V_i,A_j,B_j\leq N\ (1\leq i\leq M,1\leq j\leq K)$
• $U_i\neq V_i\ (1\leq i\leq M),\ A_j\neq B_j\ (1\leq j\leq K)$
• $1\leq S_j\leq 10^9\ (1\leq j\leq K)$

Output

Output the maximum achievable total profit as an integer.
Print a newline at the end.

Sample

4
-10 -20 100 50
1
1 3
1
1 4 30

170

3
0 -10 -20
3
2 1
2 3
3 2
1
2 3 30

0