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>.
import sys
input = sys.stdin.buffer.readline 
  
def process(m, A, Rules):
    n = len(A)
    k = len(Rules)
    d = [0 for j in range(n*2**n)]
    rule_m = [[0 for j in range(n)] for i in range(n)]
    pairs = [[] for i in range(2**n)]
    good = []
    for i in range(2**n):
        if sum(map(int, bin(i)[2:]))==m:
            good.append(i)
        for j in range(n):
            if i&(2**j) == 0:
                pairs[i].append(j)
    for x, y, c in Rules:
        rule_m[x-1][y-1] = c 
    start = []
    for i in range(n):
        d[n*2**i+i] = A[i]
        start.append(n*2**i+i)
    while len(start) > 0:
        next_s = []
        for a in start:
            a1 = a//n 
            b1 = a % n
            for b2 in pairs[a1]:
                a2 = a1|2**b2
                sat1 = (d[a]+A[b2]+rule_m[b1][b2])
                if sat1 > d[n*a2+b2]:
                    d[n*a2+b2] = sat1
                    next_s.append(n*a2+b2)
        start = next_s 
    answer = 0 
    for i1 in good:
        for i2 in range(n):
            answer = max(answer, d[n*i1+i2])
    sys.stdout.write(f'{answer}\n')
    return 
    
n, m, k = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
Rules = []
for i in range(k):
    xi, yi, ci = [int(x) for x in input().split()]
    Rules.append([xi, yi, ci])
process(m, A, Rules)