#include <bits/stdc++.h>
using namespace std ;
using ll = long long ;
const int maxN = 5005, M = 1e5 + 5 ;
const ll mod = 1e9 + 7 ;
int S , N, V[M], W[M], K[M] ;
vector<map<int,ll>> dp(2001) ;
ll solve(int i, int j) {
if (i == N) return 0ll ;
if (dp[j].count(i)) return dp[j][i] ;
ll ret = 0 ;
for (ll c = 0 ; c <= K[i] && c * W[i] <= j ; c++) {
ret = max(ret, solve(i + 1, j - c * W[i]) + c * V[i]) ;
}
dp[j][i] = ret ;
return ret ;
}
int32_t main() {
ios::sync_with_stdio(false) ;
cin.tie(nullptr) ;
cin >> S >> N ;
for (int i = 0 ; i < N ; i++) {
cin >> V[i] >> W[i] >> K[i] ;
}
cout << solve(0, S) ;
return 0 ;
}
