60pts救~~~~

#include<bits/stdc++.h>
using namespace std;
const int MAXN=65,MAXM=32e2+5;
int n,m,v[MAXN],w[MAXN],f[MAXN],num[MAXN],dp[MAXM];
int main(){
    scanf("%d%d",&m,&n);
    m/=10;
    int step=1;
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&v[i],&w[i],&f[i]);
        if(!f[i]){num[i]=step;step++;}
        v[i]/=10;w[i]*=v[i];
    }
    for(int i=1;i<=n;i++)
        if(!f[i]){
            int l1=0,l2=0;
            for(int j=1;j<=n;j++) 
                if(f[j]==num[i]){
                    if(!l1&&!l2) l1=j;
                    else l2=j;
                }
            for(int j=m;j>=v[i];j--){
                dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
                if(j-v[i]-v[l1]>=0) dp[j]=max(dp[j],dp[j-v[i]-v[l1]]+w[i]+w[l1]);
                if(j-v[i]-v[l2]>=0) dp[j]=max(dp[j],dp[j-v[i]-v[l2]]+w[i]+w[l2]);
                if(j-v[i]-v[l1]-v[l2]>=0) dp[j]=max(dp[j],dp[j-v[i]-v[l1]-v[l2]]+w[i]+w[l1]+w[l2]);
            }
        }
    printf("%d",dp[m]*10);
    return 0;
}