#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
#define int long long
#define vec vector
#define code signed main()
template<typename _T>
bool chmax(_T &a, const _T &b) {
if (a < b) {
a = b;
return true;
}
return false;
}
inline void io(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
code
{
io();
int n , m;
cin >> m >> n;
vec<int> dp(m + 1 , 0);
for (int i = 1; i <= n; i++){
int v , w , k;
cin >> v >> w >> k;
for (int x = 1; k > 0; x <<= 1){
int kol = min(k , x);
k -= kol;
int val = v * kol;
int wei = w * kol;
for (int j = m; j >= wei; j--)
chmax(dp[j] , dp[j - wei] + val);
}
}
cout << *max_element(dp.begin() , dp.end()) << "\n";
return 0;
}
