#include<stdio.h> #include<iostream> #include<algorithm> #include<string> #include<string.h> #include<math.h> #include<map> #include<queue> #include<set> #include<stack> #include<vector> #define LL long long using namespace std; struct node { int w, v; node(int a, int b) { w = a; v = b; } node() {} }; vector <node> tre[10005]; int dp[50005]; int main() { int w, n; while(~scanf("%d%d", &w, &n)) { for(int i = 0; i < 10005; i++) tre[i].clear(); memset(dp, 0, sizeof(dp)); w /= 100; int cnt = 0; for(int i = 0; i < n; i++) { int w1, v1, w2, v2, r; scanf("%d%d%d%d%d", &w1, &v1, &w2, &v2, &r); w1 /= 100; w2 /= 100; if(r == 1) tre[cnt++].push_back(node(w1 + w2, v1 + v2)); else if(r == 2) { tre[cnt].push_back(node(w1, v1)); tre[cnt++].push_back(node(w2, v2)); } else { tre[cnt].push_back(node(w1, v1)); tre[cnt++].push_back(node(w1 + w2, v1 + v2)); } } for(int i = 0; i < cnt; i++) for(int j = w; j >= 0; j--) { int ret = -1; for(int k = 0; k < tre[i].size(); k++) if(j >= tre[i][k].w) ret = max(ret, (dp[j - tre[i][k].w] + tre[i][k].v)); dp[j] = max(dp[j], ret); } int ans = 0; for(int i = 0; i <= w; i++) ans = max(ans, dp[i]); printf("%dn", ans); } return 0; }
