Description

There are $N$ Portals on the map. Now an Agent's task is to capture $M$ Portals on this map. The score gained by capturing the $i$-th Portal is $A[i]$. Besides capturing directly, there are also $K$ other bonus-scoring methods. For these $N$ Portals, after capturing the $X[i]$-th Portal, capturing the $Y[i]$-th Portal will grant an additional bonus of $B[i]$. Bonus rules may be duplicated. The Agent wants to earn more points for the team, so he asks you, the battle strategist, to help him.

Input Format

The first line contains three integers $N, M, K$. The second line contains $N$ numbers, where the $i$-th number represents $A[i]$. The next $K$ lines each contain three integers $X[i], Y[i], C[i]$, indicating that after capturing the $X[i]$-th Portal, capturing the $Y[i]$-th Portal will grant an additional bonus of $B[i]$.

Output Format

Output only one line with one integer, the maximum score this Agent can obtain.

3 2 1
1 1 1
1 2 3

5

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

6

Hint

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$.

Translated by ChatGPT 5