#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vvi vector<vi>
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int W, n;
cin >> W >> n;
vi vals(n), wes(n), copies(n);
for(int i = 0; i < n ; i ++)
{
cin >> vals[i] >> wes[i] >> copies[i];
}
// vvi dp(n + 1, vi(W + 1, 0));
vvi dp(n + 1, vi(W + 1, 0));
for(int i = 1; i <= n; i ++)
{
int &val = vals[i - 1], &we = wes[i - 1], &cop = copies[i - 1];
for(int j = 0; j <= W; j ++)
{
for(int k = 0; (k <= cop) && (k * we <= j); k ++)
dp[i][j] = max(dp[i][j], dp[i - 1][j - k * we] + k * val);
}
}
// for(int j = 0; j < W + 1; j ++)
// {
// for(int i = 1; i <= n; i ++)
// {
// int &val = vals[i - 1], &we = wes[i - 1], &cop = copies[i - 1];
// for(int k = 0; (k < cop) && (k * we <= j); k ++)
// dp[i][j] = max(dp[i][j], dp[i - 1][j - k * we] + k * val);
// }
// }
cout << dp[n][W];
}
// 第一次错误原因： 对于 k 的遍历 k <= cop
// 上面已经很完整了，对比KSol.cpp, KSol.cpp有些逻辑冗余了。
// 要优化这段多重背包问题的代码，可以使用一些经典的优化技巧来减少时间复杂度，尤其是避免在内部循环中使用重复计算。下面是一些可以应用的优化方法：
// 优化思路
// 二进制拆分法：利用二进制拆分来减少物品数量的计算。这种方法将一个物品的多个副本转化为若干个较小数量的副本，从而减少内层循环的迭代次数。
// 滚动数组：由于只需要上一行的 dp 状态，可以使用滚动数组来减少空间复杂度。
// -》 Optimize_knapsack.cpp -> 过不了，只能过17/100个样例，删了
