#pragma GCC optimize("Ofast")
#include"bits/stdc++.h"
#define int long long
using namespace std;
const int sz = 1e5 + 5;
const int sm = 2e3 + 3;
int dp[sm][sz];
bool v[sz];
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, s;
cin >> s >> n;
vector <int> a, b;
a = {0}, b = {0};
for (int i = 1; i <= n; i ++) {
int v, w, k;
cin >> v >> w >> k;
for (int j = 0; (1 << j) < k; j ++) {
a.push_back((1 << j) * v);
b.push_back((1 << j) * w);
k -= (1 << j);
}
if (0 < k) {
a.push_back(k * v);
b.push_back(k * w);
}
}
int m = a.size() - 1;
for (int i = 1; i <= m; i ++) {
cout << a[i] << ' ' << b[i] << '\n';
}
v[0] = true;
for (int i = 1; i <= m; i ++) {
for (int j = s; 0 <= j - b[i]; j --) {
if (v[j - b[i]]) {
dp[j][i] = dp[j - b[i]][i - 1] + a[i];
v[j] = true;
}
}
for (int j = s; 0 <= j; j --) {
dp[j][i] = max(dp[j][i], dp[j][i - 1]);
}
}
int mx = 0;
for (int i = 0; i <= s; i ++) {
mx = max(mx, dp[i][m]);
}
cout << mx << '\n';
}
