rt

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010, M = 2010;

int n, m;
int dp[M], g[M], q[M];

namespace IO{
    char buf[1 << 20], *p1, *p2;
    #define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, (1 << 20), stdin), p1 == p2) ? EOF : *p1++)
    template<typename T>
    inline T read() {
        T x = 0;
        char ch = gc();
        while(ch < '0' || ch > '9') ch = gc();
        while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + ch - 48; ch = gc();}
        return x;
    }
    inline void write(int x) {
        static int sta[35];
        int top = 0;
        do{
            sta[top++] = x % 10, x /= 10;
        } while(x);
        while(top) putchar(sta[--top] + 48);
    }
}
using namespace IO;

int main() {
    m = read<int>(), n = read<int>();
    for(int i = 0; i < n; i++) {
        int w, v, s;
        w = read<int>(), v = read<int>(), s = read<int>();
        s = min(s, m / v);
        memcpy(g, dp, sizeof dp);
        for(int j = 0; j < v; j++) {
            int hh = 0, tt = -1;
            for(int k = j; k <= m; k += v) {
                while(hh <= tt && (k - q[hh]) / v > s) hh++;
                if(hh <= tt) dp[k] = max(dp[k], g[q[hh]] + (k - q[hh]) / v * w);
                while(hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w) tt--;
                q[++tt] = k;
            }
        }
    }
    printf("%d", dp[m]);
    return 0;
}