#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int S, N;
cin >> S >> N;
// 1) Nhóm theo trọng số
vector<vector<int>> byW(S+1);
for(int i = 0; i < N; i++){
int V, W, K;
cin >> V >> W >> K;
// K bản giống hệt, ta push giá trị V, K lần
// nhưng thực tế đây chỉ là để minh hoạ: nếu K rất lớn,
// bạn có thể cap ngay khi push:
int cap = min(K, S / W);
while(cap--) byW[W].push_back(V);
}
// 2) Lọc giữ top ⌊S/w⌋ giá trị cho mỗi w
vector<pair<int,int>> items;
items.reserve(100000); // ước lượng
for(int w = 1; w <= S; w++){
auto &vec = byW[w];
if(vec.empty()) continue;
sort(vec.begin(), vec.end(), greater<>());
int take = min((int)vec.size(), S / w);
for(int i = 0; i < take; i++){
items.emplace_back(w, vec[i]);
}
}
// 3) Chạy 0/1 Knapsack DP
vector<ll> dp(S+1, 0);
for(auto [w, v] : items){
for(int j = S; j >= w; j--){
dp[j] = max(dp[j], dp[j-w] + v);
}
}
// 4) Kết quả: max giá trị với trọng số ≤ S
ll ans = 0;
for(int j = 0; j <= S; j++)
ans = max(ans, dp[j]);
cout << ans << "\n";
return 0;
}
