AOJ2156.cpp

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <queue>
#include <algorithm>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()
#define chmin(a, b) a=min((a),(b));

using namespace std;

const int INF = 1000000000;

vector<int> knapsackProblem(vector<pair<int,int>> w, int n) {
  vector<int> res(n, INF); res[0] = 0;
  REP(i,w.size())
    for (int j = 0; j + w[i].first < n; j++)
      chmin(res[j + w[i].first], res[j] + w[i].second);
  for (int i = n-1; i > 0; i--)
    chmin(res[i-1], res[i]);
  return res;
}

int main() {
  int N, M, mp, damage;
  string name, target;
  while (cin >> N, N) {
    vector<int> hp(N);
    vector<pair<int,int>> all, single;
    REP(i,N) cin >> hp[i];
    cin >> M;
    REP(i,M){
      cin >> name >> mp >> target >> damage;
      if (target == "All") all.emplace_back(damage, mp);
      else single.emplace_back(damage, mp);
    }
    vector<int> all_mp = knapsackProblem(all, 2000000);
    vector<int> single_mp = knapsackProblem(single, 2000000);
    long long res = INF;
    REP(v, 100010) {
      long long cnt = all_mp[v];
      REP(i,N) {
        if (hp[i] - v < 0) continue;
        cnt += single_mp[hp[i] - v];
      }
      chmin(res, cnt);
    }
    cout << res << endl;
  }
  return 0;
}