この問題は、 bit全探索 を用いることで正解できます。

bit 全探索について、詳しくは以下の記事を参照してください。他にも、 bit 全探索について解説した記事はインターネット上にたくさん存在します。

• bit全探索について簡単にまとめる
• 【入門】 基礎から理解するbit全探索

bit 全探索中に行うべきことは次の通りです。

• チームが丁度 \(K\) 人からなるか判定する。
• どのペアについてペナルティを受けるか判定する。

なお、bit全探索を用いる場合は添え字が \(0\) 始まりになるように変換すると実装が簡単になります。

実装例の時間計算量は \(O(2^N(N+M))\) で額面 \(8 \times 10^7\) となり、実行時間制限に間に合います。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int main(){
  ll N,M,K;
  cin >> N >> M >> K;
  vector<ll> A(N);
  for(auto &nx : A){cin >> nx;}
  vector<ll> U(M),V(M),B(M);
  for(ll i=0;i<M;i++){
    cin >> U[i] >> V[i] >> B[i];
    U[i]--; V[i]--;
  }
  ll best=-4e18;
  for(ll i=0;i<(1ll<<N);i++){
    ll current=0,count=0;
    for(ll j=0;j<N;j++){
      if(i&(1ll<<j)){
        current+=A[j];
        count++;
      }
    }
    if(count!=K){continue;}
    for(ll j=0;j<M;j++){
      if((i&(1ll<<U[j]))>0 && (i&(1ll<<V[j]))>0){
        current-=B[j];
      }
    }
    best=max(best,current);
  }
  cout << best << "\n";
  return 0;
}