//CHATGPT nin kodu test ucun atilmisdir
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int S, N;
cin >> S >> N; // S: sepetin alabileceği maksimum ağırlık, N: ürün türü sayısı
// dp[w] : ağırlığı w olan sepet için elde edilebilecek maksimum değer
vector<int> dp(S + 1, 0);
for (int i = 0; i < N; i++) {
int V, W, K;
cin >> V >> W >> K; // V: değer, W: ağırlık, K: kopya sayısı
// Binary splitting yöntemiyle her ürünü 0-1 knapsack alt problemlere bölüyoruz.
int num = K;
int count = 1;
while (num > 0) {
int take = min(count, num);
int value = take * V;
int weight = take * W;
// 0-1 knapsack DP güncellemesi: Ters yönde döngü (her öğeyi yalnızca bir kere kullanmak için)
for (int w = S; w >= weight; w--) {
dp[w] = max(dp[w], dp[w - weight] + value);
}
num -= take;
count *= 2;
}
}
cout << dp[S] << endl;
return 0;
}
