#include<iostream>
using namespace std;
struct thing
{
    int v;
    int p;
    int q;
    thing *f1;
    thing *f2;
}a[65];
int n, m;
bool firstf[65] = { true };
int ans;
void DFS(int k, int sumofmoney,int sum)
{
    if (sumofmoney > n)
        return;
    else if (k == m + 1)
    {
        if (sum > ans)
            ans = sum;
        return;
    }
    else if (a[k].q > 0)
    {
        DFS(k + 1, sumofmoney, sum);
        return;
    }
    DFS(k + 1, sumofmoney + a[k].v, sum + a[k].v*a[k].p);
    DFS(k + 1, sumofmoney, sum);
    if (a[k].f1 != NULL)
        DFS(k + 1, sumofmoney + a[k].v + a[k].f1->v,sum + a[k].v*a[k].p + a[k].f1->v*a[k].f1->p);
    else if(a[k].f2!=NULL)
        DFS(k + 1, sumofmoney + a[k].v + a[k].f2->v,sum + a[k].v*a[k].p + a[k].f2->v*a[k].f2->p);
    if (a[k].f2 != NULL && a[k].f1 != NULL)
        DFS(k + 1, sumofmoney + a[k].v + a[k].f1->v + a[k].f2->v, sum + a[k].v*a[k].p + a[k].f1->v*a[k].f1->p + a[k].f1->v*a[k].f1->p);
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> a[i].v >> a[i].p >> a[i].q;
        if (a[i].q > 0)
        {
            if (firstf[i])
            {
                a[a[i].q].f1 = &a[i];
                firstf[i] = false;
            }
            else
                a[a[i].q].f2 = &a[i];
        }
    }
    DFS(1, 0, 0);
    cout << ans;
}