#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
struct {
        int v,p,e;
        int v2,p2,e2;
        int v3,p3,e3;
}w[61];
int main() {
        int n,m,cnt = 0,f[32001];
        memset(f,0,sizeof(f));
        memset(w,0,sizeof(w));
        scanf("%d%d",&n,&m);
        for (int i = 1,v,p,q;i <= m;i++) {
                scanf("%d%d%d",&v,&p,&q);
                if (!q) {
                    w[++cnt].v = v;
                    w[cnt].p = p;
                    w[cnt].e = v*p;
                } else
                    if (!w[q].v2 && !w[q].p2 && !w[q].e2) {
                        w[q].v2 = v;
                        w[q].p2 = p;
                        w[q].e2 = v*p;
                    } else {
                        w[q].v3 = v;
                        w[q].p3 = p;
                        w[q].e3 = v*p;
                    }
        }
        for (int i = 1;i <= cnt;i++)
                for (int j = n;j >= w[i].v;j--) {
                    f[j] = max(f[j],f[j-w[i].v]+w[i].e);
                    if (j-w[i].v-w[i].v2 >= 0) f[j] = max(f[j],f[j-w[i].v-w[i].v2]+w[i].e+w[i].e2);
                    if (j-w[i].v-w[i].v3 >= 0) f[j] = max(f[j],f[j-w[i].v-w[i].v3]+w[i].e+w[i].e3);
                    if (j-w[i].v-w[i].v2-w[i].v3 >= 0) f[j] = max(f[j],f[j-w[i].v-w[i].v2-w[i].v3]+w[i].e+w[i].e2+w[i].e3);
            }
        printf("%d",f[n]);
        return 0;
}