#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
int p[maxn];
int v[maxn];
int tot[maxn];
int dp[1010];
int main(){

 int x,n;
 scanf("%d%d",&x,&n);
 for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&p[i],&tot[i],&v[i]);
    }
    int k = n + 1;
    for (int i = 1; i <= n; i++) {
        while (tot[i] != 1) {
            p[k] = p[i];
            v[k] = v[i];
            k++;
            tot[i]--;
        }
    }
    for (int i = 1; i <= k; i++)
    {
        for (int j = x; j >= 1; j--)
        {
            if (p[i] <= j)
                dp[j] = max(dp[j], dp[j - p[i]] + v[i]);
        }
    }
    int ans=0;
    for(int i=1;i<=x;i++)
    {
        //cout<<dp[i]<<endl;
        ans=max(ans,dp[i]);
    }
    cout<<ans<<endl;
 return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
int a[110];
int dp[10010];

int main()
{
    int x,n;
    scanf("%d%d",&x,&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",a+i);
    }
    dp[0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=x;j>=1;j--)
        {
            if(a[i]<=j)
            {
                dp[j]+=dp[j-a[i]];
            }
        }
    }
    if(dp[x])
        cout<<dp[x]<<endl;
    else
        cout<<-1<<endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100+10;
int a[maxn][maxn];
int n,m;
int dir[4][2]={0,1,0,-1,1,0,-1,0};
int stx,sty,enx,eny;
struct node
{
    int x,y,v,pr;
    node(){};
    node(int x,int y,int v,int pr):x(x),y(y),v(v),pr(pr){};
    friend bool operator <(const node &t1,const node &t2)
    {
        if(t1.v==t2.v)
        {
            if(t1.x==t2.x)
                return t1.y<t2.y;
            return t1.x<t2.x;
        }
        return t1.v>t2.v;
    }
};
int vis[maxn][maxn][4];
bool check(int x,int y,int i)
{
    if(x>=0&&x<n&&y>=0&&y<m&&a[x][y]==0&&vis[x][y][i]==0)
        return true;
    return false;
}
priority_queue<node> pq;
int bfs()
{
    pq.push(node(stx,sty,0,-1));
    for(int i=0;i<4;i++)
        vis[stx][sty][i]=1;
    while(pq.size())
    {
        node now = pq.top();
        pq.pop();
        if(now.x==enx&&now.y==eny)
            return now.v;
        for(int i=0;i<4;i++)
        {
            int x1=now.x+dir[i][0],y1=now.y+dir[i][1];
            if(x1==enx&&y1==eny)
            {
                if(i!=now.pr)
                    return now.v+1;
                return now.v;
            }
            if(check(x1,y1,i))
            {
                int step=now.v;
                if(i!=now.pr)
                {
                    step++;
                }
                pq.push(node(x1,y1,step,i));
                vis[x1][y1][i]=1;
            }
        }
    }
    return -1;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    scanf("%d%d%d%d",&stx,&sty,&enx,&eny);
    cout<<bfs()<<endl;
    return 0;
}