#include <bits/stdc++.h>
using namespace std;
int w, n;
int copies[100001] = {};
int arr[100001][2] = {};
int dp[100001][2001] = {};
int ans (int pos, int cur) {
int &ret = dp[pos][cur];
if (ret != -1) return ret;
if (pos == 0 || cur == 0) return ret = 0;
if (arr[pos][0] > cur) {
return ret = ans(pos - 1, cur);
}
int p = ans(pos - 1, cur);
for (int i = 1; arr[pos][0] * i <= cur && i <= copies[pos]; i++) {
p = max(p, i * arr[pos][1] + ans(pos - 1, cur - i * arr[pos][0]));
}
return ret = p;
}
int main () {
memset(dp, -1, sizeof(dp));
cin >> w >> n;
for (int i = 1; i <= n; i++) {
cin >> arr[i][1] >> arr[i][0] >> copies[i];
}
cout << ans(n, w) << endl;
}
