#include <iostream> #include <queue> using namespace std; priority_queue<double> heap; double ans; //深搜回溯求最大和 //直接贪心取值无法ac,浮点数没法dp //把money都乘以100,小数点后两位映射到整数,就可以背包 void dfs(double sum, double q) { if(sum > q) return; else ans = max(ans, sum); if(heap.empty()) return; double tmp = heap.top(); heap.pop(); //当前堆顶是否加入sum中进行深搜 dfs(sum, q), dfs(sum + tmp, q); heap.push(tmp); } bool valid(char a, double p) { if(a == 'A' || a == 'B' || a == 'C') return p <= 600.00; return false; } int main() { double q; int n, m; bool flag; while (cin >> q >> n && n) { // 注意 while 处理多个 case heap = priority_queue<double>(); while(n --) { flag = true; cin >> m; double sum = 0.0; while(m --) { char a, b; double p; cin >> a >> b >> p; flag &= valid(a, p); sum += p; } if(flag && sum <= 1000 && sum <= q) { heap.push(sum); // cout <<"valid : " <<sum << endl; } } ans = 0; dfs(0.0, q); printf("%.2lf\n", ans); } } // 64 位输出请用 printf("%lld")