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>.
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    int n,m,k;
    cin>>n>>m>>k;
    vector<int> a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    int total=(1<<n)+1;
    ll dp[total+1][n+1];
    int c[n+1][n+1];
    for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)c[i][j]=0;
    for(int i=1;i<=k;i++){
        int x,y,val;cin>>x>>y>>val;
        c[x-1][y-1]=val;
    }
    for(int i=0;i<=total;i++)for(int j=0;j<=n;j++)dp[i][j]=0;
    for(int i=0;i<n;i++)dp[(1<<i)][i]=a[i];
    for(int i=0;i<(1<<n);i++){
        for(int j=0;j<n;j++){
            if(i&(1<<j)){
                for(int k=0;k<n;k++){
                    if((i&(1<<k))==0){
                        dp[(i|(1<<k))][k]=max(dp[(i|(1<<k))][k],dp[i][j]+c[j][k]+a[k]);
                        
                    }
                }
            }
        }
       
    }
    ll ans=0LL;
    for(int i=0;i<(1<<n);i++){
        int tmp=i;
        int ct=0;
        for(int j=0;j<n;j++){
            if(tmp&(1<<j)){ct++;}
        }
        if(ct==m){
            for(int j=0;j<n;j++){
                
                ans=max(ans,dp[i][j]);
            }
        }
       
    }
    cout<<ans<<"\n";
    
}
