部分集合 \(s\) を含む集合全体に \(+p\) 点というような条件が分かっているとします。
すると、 高速ゼータ変換 の要領で各部分集合に対するスコアを時間計算量 \(O(2^N)\) で計算できます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int main(){
  ll N,M,K;
  cin >> N >> M >> K;
  vector<ll> z(1ll<<N,0);
  vector<ll> A(N);
  for(ll i=0;i<N;i++){
    cin >> A[i];
    z[(1ll<<i)]+=A[i];
  }
  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]--;
    z[(1ll<<U[i])|(1ll<<V[i])]-=B[i];
  }
  for(ll d=0;d<N;d++){
    for(ll i=0;i<(1ll<<N);i++){
      if(i&(1ll<<d)){
        z[i]+=z[i^(1ll<<d)];
      }
    }
  }
  ll res=-8e18;
  for(ll i=0;i<(1ll<<N);i++){
    if(__builtin_popcountll(i)==K){
      res=max(res,z[i]);
    }
  }
  cout << res << "\n";
  return 0;
}