#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
using namespace std;
#define F first
#define S second
typedef long long ll;
#define pii pair <int, int>
#define pll pair <ll, ll>
typedef long double ld;
const ll N = 2000 + 100, M = 4096 + 10, len = 21, inf = 1e18;
const ll mod = 1e9 + 7;
ll dp[N], val, ans;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int s, n, w, k;
cin >> s >> n;
for(int i = 0; i <= s; i++){
dp[i] = -1;
}
dp[0] = 0;
for(int i = 0; i < n; i++){
cin >> val >> w >> k;
while(k--){
bool was = false;
for(int j = s; j >= w; j--){
if(dp[j - w] == -1) continue;
if(dp[j - w] + val > dp[j]){
was = true;
dp[j] = dp[j - w] + val;
}
}
if(was ==false) break;
}
}
for(int i = 0; i <= s;i++){
ans = max(ans, dp[i]);
}
cout << ans;
return 0;
}
