When Kefa came to the restaurant and sat at a table, the waiter immediately brought him the menu. There were *n* dishes. Kefa knows that he needs exactly *m* dishes. But at that, he doesn't want to order the same dish twice to taste as many dishes as possible. 

Kefa knows that the *i*-th dish gives him *a*<sub class="lower-index">*i*</sub> units of satisfaction. But some dishes do not go well together and some dishes go very well together. Kefa set to himself *k* rules of eating food of the following type — if he eats dish *x* exactly before dish *y* (there should be no other dishes between *x* and *y*), then his satisfaction level raises by *c*. 

Of course, our parrot wants to get some maximal possible satisfaction from going to the restaurant. Help him in this hard task!
The first line of the input contains three space-separated numbers, *n*, *m* and *k* (1 ≤ *m* ≤ *n* ≤ 18, 0 ≤ *k* ≤ *n* * (*n* - 1)) — the number of dishes on the menu, the number of portions Kefa needs to eat to get full and the number of eating rules.

The second line contains *n* space-separated numbers *a*<sub class="lower-index">*i*</sub>, (0 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>) — the satisfaction he gets from the *i*-th dish.

Next *k* lines contain the rules. The *i*-th rule is described by the three numbers *x*<sub class="lower-index">*i*</sub>, *y*<sub class="lower-index">*i*</sub> and *c*<sub class="lower-index">*i*</sub> (1 ≤ *x*<sub class="lower-index">*i*</sub>, *y*<sub class="lower-index">*i*</sub> ≤ *n*, 0 ≤ *c*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>). That means that if you eat dish *x*<sub class="lower-index">*i*</sub> right before dish *y*<sub class="lower-index">*i*</sub>, then the Kefa's satisfaction increases by *c*<sub class="lower-index">*i*</sub>. It is guaranteed that there are no such pairs of indexes *i* and *j* (1 ≤ *i* &lt; *j* ≤ *k*), that *x*<sub class="lower-index">*i*</sub> = *x*<sub class="lower-index">*j*</sub> and *y*<sub class="lower-index">*i*</sub> = *y*<sub class="lower-index">*j*</sub>.
# ﷽
from collections import defaultdict
import sys
input = lambda: sys.stdin.readline().strip()
def inlst():return [int(i) for i in input().split()]

def solve():
    n,m,k=inlst()
    lst=inlst()
    d=defaultdict(int)
    ans=0
    for _ in range(k):
        x,y,c=inlst()
        d[(x-1,y-1)]=c

    dp=[[0]*n for _ in range(1<<n) ]
    for i in range(n):dp[1<<i][i]=lst[i]
    for mask in range(1,1<<n):
        for i in range(n):
            if  ((mask>>i)&1):continue # need 0  i=>0
            for j in range(n):
                if not (mask>>j)&1:continue # need 1  j=>1 
                dp[mask|(1<<i)][i]=max(dp[mask|(1<<i)][i],dp[mask][j]+lst[i]+d[(j,i)])
       
    for mask in range(1<<n):
        if mask.bit_count()!=m:continue
        for i in range(n):
            ans=max(ans,dp[mask][i])
    
    
    print(ans)


if __name__ == "__main__":
    # for _ in range(int(input())):
        solve()
