Background

The XM Battle is arriving as scheduled. The Agents gather together for the final showdown. There are many ways to fight, and some complicated methods can earn higher scores. Unfortunately, the people from ENLIGHTENED are not very smart and only know simple hack, so the ENLIGHTENED operation commander asked you to be their chief strategist.

Problem 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