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>.
/*
	Name: 
	Copyright: 
	Author: 
	Date: 10/06/23  16:20
	Description: https://codeforces.com/problemset/problem/580/D
*/

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 114514;
const int N = 2e5+1;
#define x first
#define y second 
#define endl '\n'
#define all(x)	(x).begin(),(x).end()
typedef pair<int,int> pii;
int n, m, k, q;
unordered_map<ll,ll> mp;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m >> k;
	ll a[n+1];
	ll b[n+1];
	ll g[n+1][n+1];
	memset(g,0,sizeof g);
	for(int i = 1; i <= n; ++i)	cin >> a[i];
	for(int i = 1; i <= k; ++i){
		int x, y, z;
		cin >> x >> y >> z;
		g[x][y] = z;
	}
	ll dp[(1<<n)][n+1];
	memset(dp,0,sizeof dp);
	
	for(int i = 1; i <= n; ++i)	b[i] = (ll)pow(2,i-1);
	for(int i = 1; i <= n; ++i)	dp[b[i]][i] = a[i];
	for(ll k = 0; k < (1<<n); ++k){
		for(int i = 1; i <= n; ++i){
			if(b[i]&k){
				for(int j = 1; j <= n; ++j){
					if((b[j]&k) == 0){
						
						dp[b[j]|k][j] = max(dp[b[j]|k][j],dp[k][i]+a[j]+g[i][j]);
					}
				}
			}
		}
	}
	ll res = 0;
	for(ll i = (1<<n)-1; i; i--)
		for(int j = 1; j <= n; ++j)
			if(__builtin_popcountll(i) == m)	res = max(res,dp[i][j]);

	cout << res;
	return 0;
}