#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int S, N;
cin >> S >> N;
// Toplam değerler büyük olabileceğinden dp dizisini long long olarak tanımlıyoruz.
vector<long long> dp(S + 1, 0);
for(int i = 0; i < N; i++){
int V, W, K;
cin >> V >> W >> K; // V: ürünün değeri, W: ağırlığı, K: kopya sayısı.
int count = 1;
while(K > 0){
int take = min(count, K);
int weight = take * W;
long long value = (long long)take * V;
// Eğer oluşturulan ağırlık S'den büyükse, döngü çalışmaz
for(int j = S; j >= weight; j--){
dp[j] = max(dp[j], dp[j - weight] + value);
}
K -= take;
count *= 2;
}
}
cout << dp[S] << "\n";
return 0;
}
