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>.
# LUOGU_RID: 112635382
import itertools
from itertools import combinations
nmk=input().split()
n=int(nmk[0])
m=int(nmk[1])
k=int(nmk[2])
a=input().split()
a=[int(c) for c in a]
f=[]
cb=0
ff=[]
for i in range(k):
    f=f+[[int(c) for c in input().split()]]
#print('f',f)
for i in f:
    ff=ff+[(i[0],i[1])]
com = [list(c) for c in  combinations(range(n), m)]
#print("com",com)
for i in com:
    
    tmp=[list(c) for c in itertools.permutations(i)]
    #print("tmp",tmp)
    for j in range(len(tmp)):
        tmp2=a[tmp[j][0]]
        for k in range(len(tmp[0])-1):
            #print('tmp[j],tmp2',tmp[j],tmp2)
            if (tmp[j][k+1]+1,tmp[j][k]+1)in ff:
                #print("if")
                #print("index",f[ff.index((tmp[j][k+1]+1,tmp[j][k]+1))][2],a[tmp[j][k+1]])
                tmp2=tmp2+a[tmp[j][k+1]]+f[ff.index((tmp[j][k+1]+1,tmp[j][k]+1))][2]
            else:
                #print("el")
                tmp2=tmp2+a[tmp[j][k+1]]
            #print("tmp2",tmp2)
        #print("tmp22",tmp2)
        cb=max(cb,tmp2)
print(cb)
#print(cb)
#li=list(itertools.permutations(com))
