#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; // 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: ürünün değeri, W: ağırlığı, K: kopya sayısı.
// Binary splitting yöntemi: Kopya sayısını ikili parçalara bölerek 0-1 knapsack'a dönüştürüyoruz.
int count = 1;
while(K > 0){
int take = min(count, K);
int value = take * V;
int weight = take * W;
// Ağırlık sınırını ters döngü ile güncelleyin; böylece her parçayı yalnızca bir kere kullanırız.
for(int j = S; j >= weight; j--){
dp[j] = max(dp[j], dp[j - weight] + value);
}
K -= take;
count *= 2;
}
}
// Maksimum değeri yazdırıyoruz.
cout << dp[S] << "\n";
return 0;
}
