#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2003;
int dp[N];
vector<pair<int, int>> a;
void solve() {
int S, N; cin >> S >> N;
for(int i = 0; i < N; ++i){
int v, w, k; cin >> v >> w >> k;
for(int j = 1; j <= k; j*=2){
// if(j * w <= S) a[j * w] = max(a[j * w], j * v);
if(j * w <= S) a.push_back({j * w, j * w});
k -= j;
}
// if(k > 0 && k * w <= S) a[k * w] = max(a[k * w], k * v);
if(k > 0 && k * w <= S) a.push_back({k * w, k * w});
}
for(int i = 0; i < a.size(); ++i){
auto [w, v] = a[i];
for(int j = S-w; j >= 0; --j)
dp[j+w] = max(dp[j+w], dp[j] + v);
}
cout << *max_element(dp, dp + S + 1) << "\n";
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
// freopen("feast.in", "r", stdin);
// freopen("feast.out", "w", stdout);
int tc = 1;
// cin >> tc;
while(tc--) solve();
}
