#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int S, N;
cin >> S >> N; // Đọc trọng lượng tối đa và số loại vật
vector<int> dp(S + 1, 0); // Khởi tạo mảng DP, dp[j] = giá trị tối đa với trọng lượng j
// Xử lý từng loại vật
for (int i = 0; i < N; i++) {
int V, W, K;
cin >> V >> W >> K; // Đọc giá trị, khối lượng, số lượng của loại vật thứ i
// Phân tích nhị phân cho loại vật này
int count = 1;
while (K > 0) {
int num = min(count, K); // số lượng trong nhóm hiện tại (1, 2, 4, ..., hoặc phần còn lại)
int groupValue = num * V; // giá trị của nhóm vật này
int groupWeight = num * W; // khối lượng của nhóm vật này
// Cập nhật DP như 0/1 knapsack với vật có giá trị groupValue và khối lượng groupWeight
for (int j = S; j >= groupWeight; j--) {
dp[j] = max(dp[j], dp[j - groupWeight] + groupValue);
}
K -= num; // Giảm bớt số lượng đã gộp vào nhóm
count <<= 1; // Nhân đôi count cho nhóm tiếp theo (1 -> 2 -> 4 -> ...)
}
}
// Kết quả là giá trị tối đa với trọng lượng không vượt quá S
cout << dp[S] << "\n";
return 0;
}
