Background

The XM War has begun as scheduled, and Agents have gathered to engage in the final showdown. There are various ways to battle, with some complex methods yielding higher scores. Unfortunately, the ENLIGHTENED agents are not very clever and only know how to perform simple hacks. Therefore, the ENLIGHTENED Operation Commander has sought you out to serve as their chief strategist.

Problem Description

On the map, there are $N$ Portals. An Agent's mission is to capture $M$ of these Portals. The score obtained by the Agent for capturing the $i$-th Portal is $A[i]$. In addition to direct captures, there are $K$ other ways to gain extra points. For these $N$ Portals, capturing the $X[i]$-th Portal followed by the $Y[i]$-th Portal can earn an additional $B[i]$ points. These extra points may overlap. The Agent hopes to secure the highest possible score for the team and has requested your assistance as the war strategist.

Input Format

The first line contains three integers $N, M, K$.
The second line contains $N$ numbers, where the $i$-th number represents the value of $A[i]$.
The following $K$ lines each contain three integers $X[i], Y[i], C[i]$, indicating that capturing the $X[i]$-th Portal followed by the $Y[i]$-th Portal can earn $B[i]$ additional points.

Output Format

Output a single integer, which is the maximum score the Agent can achieve.

Sample Input and Output

Sample Input #1

3 2 1
1 1 1
1 2 3

Sample Output #1

5

Sample Input #2

4 3 2
1 1 1 1
4 3 2
3 2 1

Sample Output #2

6

Notes

For $20\%$ of the data, $1 \leq M \leq N \leq 4, 0 \leq A[i], B[i] \leq 10^3$.

For $40\%$ of the data, $1 \leq M \leq N \leq 8, 0 \leq A[i], B[i] \leq 10^5$.

For $60\%$ of the data, $1 \leq M \leq N \leq 12, 0 \leq A[i], B[i] \leq 10^7$.

For $100\%$ of the data, $1 \leq M, X[i], Y[i] \leq N \leq 18, 0 \leq K \leq N^2 - N, 0 \leq A[i], B[i] \leq 10^9$.

见题面 Input 部分

见题面 Output 部分