#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll V[100000],W[100000],Q[100000];
ll dp[10000][10000];
ll A[100000][3];
int main()
{
    ll n,m;
    scanf("%lld%lld",&m,&n);
    for (ll i = 1; i <= n; i ++)
    {
        scanf("%lld%lld%lld",&V[i],&W[i],&Q[i]);
        if (Q[i])
        {
            A[i][0] ++;
            A[i][A[i][0]] = i;
        }
        W[i] *= V[i];
    }
    for (ll i = 1; i <= n; i ++)
    {
        for (ll j = 1; j <= m; j ++)
        {
            dp[i][j] = dp[i - 1][j];
            if (j >= V[i]) dp[i][j] = max(dp[i][j],dp[i - 1][j - V[i]] + W[i]);
            if (j >= V[i] + V[A[i][1]]) dp[i][j] = max(dp[i][j],dp[i - 2][j - V[i] - V[A[i][1]]] + W[i] + W[A[i][1]]);
            if (j >= V[i] + V[A[i][2]]) dp[i][j] = max(dp[i][j],dp[i - 2][j - V[i] - V[A[i][2]]] + W[i] + W[A[i][2]]);
            if (j >= V[i] + V[A[i][1]] + V[A[i][2]]) dp[i][j] = max(dp[i][j],dp[i - 3][j - V[i] - V[A[i][1]] - V[A[i][2]]] + W[i] + W[A[i][1]] + W[A[i][2]]);
        }
    }
    printf("%lld",dp[n][m]);
    return 0;
}

好人一生平安