#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
int main() {
// Tezkor kiritish va chiqarish
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int S, N;
if (!(cin >> S >> N)) return 0;
// dp[w] - w og'irlikda to'plash mumkin bo'lgan maksimal qiymat
vector<ll> dp(S + 1, 0);
for (int i = 0; i < N; i++) {
int v, w;
ll k;
cin >> v >> w >> k;
// Ikkilik ajratish (Binary Splitting)
// k dona mahsulotni 1, 2, 4, 8... kabi guruhlarga bo'lamiz
for (ll j = 1; k > 0; j <<= 1) {
ll num = min(j, k);
ll current_v = num * v;
ll current_w = num * w;
// Agar paket og'irligi savatdan katta bo'lsa, o'tkazib yuboramiz
if (current_w > S) {
k -= num;
continue;
}
// 0/1 Knapsack mantiqi: orqadan oldinga qarab yangilaymiz
for (int weight = S; weight >= (int)current_w; weight--) {
dp[weight] = max(dp[weight], dp[weight - (int)current_w] + current_v);
}
k -= num;
}
}
// Savat sig'imi ichidagi maksimal qiymatni topamiz
ll result = 0;
for (int i = 0; i <= S; i++) {
result = max(result, dp[i]);
}
cout << result << endl;
return 0;
}
