Dr. Wells decided to speed up flash. He gave flash N powers to chose from. But flash knows he requires exactly M powers. Each power i has got an intensity level Ai associated with it. There are K rules defined for taking powers : If he take power x exactly before y , his intensity level raises by c units.

Help Flash to maximize his intensity level.

First line contains 3 integers N,M and K which are already defined above.
Second line contains N integers A1,A2,....,AN denoting intensity level of each power.
Next K lines contains rules. Rach rule contains 3 integers x,y and c.

Output the maximum intensity level Flash can reach.

SAMPLE INPUT
2 2 1
1 1
2 1 1

SAMPLE OUTPUT
3

Explanation

It is good to first have the second power, then the first one. Then we get one unit of intensity for each power and one more as per the rule.

见题面

见题面