//将每种物品的个数进行拆解，从而将多重背包转化成01背包
#include <iostream>
using namespace std;

int main()
{
int n, m, i, j, k, x;
int ww, cc, ss;
int w[10010] = {0};
int c[10010] = {0};
int f[10010] = {0};
cin >> n >> m;
int cnt = 0;
for (i = 0; i < m; ++i)
{
cin >> ww >> cc >> ss;
j = 1;
while (ss > j)
{
ss -= j;
w[cnt] = ww * j;
c[cnt] = cc * j;
++cnt;
j <<= 1;
}
w[cnt] = ww * ss;
c[cnt] = cc * ss;
++cnt;
}
for (i = 0; i < cnt; ++i)
for (x = n; x >= w[i]; --x)
if (f[x - w[i]] + c[i] > f[x])
f[x] = f[x - w[i]] + c[i];
cout << f[n] << endl;
return 0;
}

//三重循环枚举个数，3个点超时
#include <iostream>
using namespace std;

int mmax(int a, int b)
{
return a > b ? a : b;
}

int main()
{
int n, m, i, j, k;
int v[10010] = {0};
int w[10010] = {0};
int s[10010] = {0};
int f[10010] = {0};
cin >> n >> m;
for (i = 0; i < m; ++i)
cin >> v[i] >> w[i] >> s[i];
for (i = 0; i < m; ++i)
for (j = n; j >= 0; --j)
for (k = 0; k <= s[i]; ++k)
{
if (j - k * v[i] < 0) break;
f[j] = mmax(f[j], f[j - k * v[i]] + w[i] * k);
}
cout << f[n] << endl;
return 0;
}

#include <iostream>
using namespace std;

int main()
{
int n, m, i, j, k, x;
int ww, cc, ss;
int w[10010] = {0};
int c[10010] = {0};
int f[10010] = {0};
cin >> n >> m;
int cnt = 0;
for (i = 0; i < m; ++i)
{
cin >> ww >> cc >> ss;
j = 1;
while (ss > j)
{
ss -= j;
w[cnt] = ww * j;
c[cnt] = cc * j;
++cnt;
j <<= 1;
}
w[cnt] = ww * ss;
c[cnt] = cc * ss;
++cnt;
}
for (i = 0; i < cnt; ++i)
for (x = n; x >= w[i]; --x)
if (f[x - w[i]] + c[i] > f[x])
f[x] = f[x - w[i]] + c[i];
cout << f[n] << endl;
return 0;
}