問題文

あなたは巨大企業の戦略コンサルタントです。
現在、$N$ 個の都市で、それぞれ新しい事業を立ち上げるかどうかの意思決定を迫られています。
計画は以下の要素から構成されます。

• 単独事業:
  都市 $i$ で事業を単独で行った場合、純利益（または純損失）として $P_i$ が得られます。
  $P_i$ は負の値になることもあります。
• 生産フロー (依存関係):
  $M$ 個の生産フロー $U\rightarrow V$ が存在します。
  これは「都市 $V$ での事業は都市 $U$ の生産物を原材料として利用する」ことを意味します。
  したがって、都市 $V$ で事業を行うためには、必ず都市 $U$ でも事業を行う必要があります。
  この依存関係は循環している可能性もあります。
• 事業提携 (シナジー):
  $K$ 種類の「事業提携」の機会があります。
  $j$ 番目の提携は都市のペア $(A_j, B_j)$ に関するもので、もし両方の都市で事業を行った場合にのみ、追加で $S_j$ のシナジー利益が発生します。

あなたは、どの都市で事業を行うかを選択し、総利益を最大化することを目指します。
なお、総利益は「 $($ 選択した事業の $P_i$ の合計 $)+($ 条件を満たした事業提携の $S_j$ の合計 $)$ 」で求まります。
達成可能な最大の総利益を求めてください。

入力

$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 N,1\leq j\leq K)$
• $U_i\neq V_i\ (1\leq i\leq N),\ A_j\neq B_j\ (1\leq j\leq K)$
• $1\leq S_j\leq 10^9\ (1\leq j\leq K)$

出力

達成可能な最大の総利益を整数で出力してください。
最後に改行してください。

サンプル

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