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.