#4WA，求大佬指正

#include <iostream>
#include <cmath>
using namespace std;
const int maxn = 100;
int w[maxn][3], val[maxn][3], itno[maxn];
//itno=item no.第i组共有多少件
int sum[maxn][35001];
int n, m;
//i 主件； j 剩下的钱
void dp()
{
    for (int i = 1; i <= m; i++)
    {
        for (int j = n; j >= w[i][0]; j--)
        {
            sum[i][j] = sum[i - 1][j];
            //first,main items
            sum[i][j] = max(sum[i][j], sum[i - 1][j - w[i][0]] + val[i][0]);
            if (itno[i] >= 2)
            {
                //then appendix 1
                if (j - w[i][1] - w[i][0] >= 0)
                    sum[i][j] = max(sum[i][j], sum[i - 1][j - w[i][1] - w[i][0]] + val[i][1] + val[i][0]);
            }
            if (itno[i] == 3)
            {
                //appendix 2
                if (j - w[i][2] - w[i][0] >= 0)
                    sum[i][j] = max(sum[i][j], sum[i - 1][j - w[i][2] - w[i][0]] + val[i][2] + val[i][0]);
                //both 1&2
                if (j - w[i][1] - w[i][0] - w[i][2] >= 0)
                    sum[i][j] = max(sum[i][j], sum[i - 1][j - w[i][1] - w[i][2] - w[i][0]] + val[i][1] + val[i][2] + val[i][0]);
            }
        }
    }
    std::cout << sum[m][n];
}
int main()
{
    int v, p, q;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> v >> p >> q;
        if (!q)
        {

            w[i][0] = v;
            val[i][0] = v * p;
            itno[i]++;

        }
        else
        {
            w[q][itno[q]] = v;
            val[q][itno[q]] = v * p;
            itno[q]++;
        }
    }
    dp();
}