P4941 War2

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.

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.

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 only one line with one integer, the maximum score this `Agent` can obtain.

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