以下の bitDP でこの問題を解くことができます。

\(dp[\) 現在警備できている施設の集合 \(S\) \(]=\{\) その状態に至る最小の費用 \(\}\)

着目している警備会社を採用する場合、その警備会社が警備できる施設の集合を \(T\) 、契約費用を \(C\) として \(dp[S \cup T]\) に \(dp[S]+C\) を遷移させればよいです。

時間計算量は \(O(2^MN)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int main(){
  int N,M;
  cin >> N >> M;
  vector<ll> C(N);
  for(auto &nx : C){cin >> nx;}

  vector<ll> dp(1<<M,4e18);
  dp[0]=0;
  for(int i=0;i<N;i++){
    int f=0;
    for(int j=0;j<M;j++){
      int E;
      cin >> E;
      f|=(E<<j);
    }
    for(int j=0;j<(1<<M);j++){
      dp[j|f]=min(dp[j|f],dp[j]+C[i]);
    }
  }

  ll res=dp[(1<<M)-1];
  if(res>2e18){res=-1;}
  cout << res << "\n";
  return 0;
}