/* poj 1821 n*n*m 暴力*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define maxn 110

#define maxm 16010

using namespace std;

int n,m,f[maxn][maxm],ans;

struct node{

    int l,s,p;

    bool operator < (const node &x) const {

        return s<x.s;

    }

}a[maxn];

int max(int x,int y){

    return x>y?x:y;

}

int main()

{

    while(~scanf("%d%d",&n,&m)){

        for(int i=;i<=m;i++)

            scanf("%d%d%d",&a[i].l,&a[i].p,&a[i].s);

        memset(f,,sizeof(f));ans=;

        sort(a+,a++m);//排序s为关键字

        for(int i=;i<=m;i++){//状态表示 前i个人 干到j这里 的最优值

            int x=min(n,a[i].s+a[i].l-);//i最多干到哪

            for(int j=;j<=n;j++){

                f[i][j]=max(f[i][j-],f[i-][j]);//i不干j 可以是j-1的状态 也可以是上一个人干到j的状态

                if(j<a[i].s||j>x)continue;//i必须停在这个范围里 也就是状态在这个范围

                for(int k=;k<a[i].s;k++){//上一个人 i-1 他不能把i的起点覆盖了 否则i就走不了了

                    if(j-k>a[i].l)continue;//i要把k-j的都盖了 长度有限制

                    f[i][j]=max(f[i][j],f[i-][k]+(j-k)*a[i].p);

                }

                ans=max(ans,f[i][j]);

            }

        }

        printf("%d\n",ans);

    }

    return ;

}

/*

poj 1821 单调队列优化

wa到挺了.....

一开始队列指针写错了...

好吧平时用STL最近手打在改习惯改乱了.

开始一直混乱着

不知道怎么保证队列里存的是i-1的状态而不是i的

根据方程的含义来看 上次不能盖了这次的s 这次还至少到s

正好分开了 多以存的时候分开

第一个for是存i-1的状态

后一个是更新i

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define maxn 110

#define maxm 16010

using namespace std;

int n,m,f[maxn][maxm],ans;

int q[maxm],head,tail;

struct node{

    int l,s,p;

    bool operator < (const node &x) const {

        return s<x.s;

    }

}a[maxn];

int max(int x,int y){

    return x>y?x:y;

}

int main()

{

    while(~scanf("%d%d",&n,&m)){

        for(int i=;i<=m;i++)

            scanf("%d%d%d",&a[i].l,&a[i].p,&a[i].s);

        memset(f,,sizeof(f));ans=;

        sort(a+,a++m);

        for(int i=;i<=m;i++){

            head=;tail=;

            for(int j=;j<=n;j++)

                f[i][j]=max(f[i-][j],f[i][j-]);

            int L=max(,a[i].s-a[i].l);

            int R=min(n,a[i].s+a[i].l-);

            for(int j=L;j<a[i].s;j++){

                int x=f[i-][j]-j*a[i].p;

                while(head<=tail&&f[i-][q[tail]]-q[tail]*a[i].p<x)tail--;

                q[++tail]=j;

            }

            for(int j=a[i].s;j<=R;j++){

                while(head<=tail&&j-q[head]>a[i].l)head++;

                int y=q[head];

                f[i][j]=max(f[i][j],f[i-][y]+(j-y)*a[i].p);//这里要取大

                ans=max(ans,f[i][j]);

            }

        }

        printf("%d\n",ans);

    }

    return ;

}