Maximize Portal Occupation Score

An agent is assigned to occupy exactly M out of N portals on a map. Each portal i gives a base score of \(A[i]\) when occupied. In addition to the base scores, there are K bonus rules. Each bonus rule is represented by three integers \(X, Y, B\) which means that if the agent occupies portal \(X\) and later occupies portal \(Y\) (note that the order matters), an extra bonus of \(B\) points is awarded. The portals must be occupied in increasing order of their indices. Calculate the maximum total score (base scores plus bonus scores) the agent can obtain by selecting exactly M portals in increasing order.

Note: If multiple bonus rules apply, all corresponding bonus points are added.

inputFormat

The input consists of:

N M K
A[1] A[2] ... A[N]
X[1] Y[1] B[1]
X[2] Y[2] B[2]
... (K lines in total)

Where \(N\) is the number of portals, \(M\) is the number of portals to be occupied, and \(K\) is the number of bonus rules. \(A[i]\) is the base score for portal i. Each bonus rule indicates that after occupying portal \(X[i]\), subsequently occupying portal \(Y[i]\) (with \(X[i] < Y[i]\)) grants an extra bonus of \(B[i]\) points. It is guaranteed that there is at least one valid selection of portals.

outputFormat

Output a single integer which is the maximum total score obtainable.

sample

5 3 2
1 2 3 4 5
1 3 10
3 5 20

39