#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct Item {
int profit, weight, copies;
// Default constructor
Item() {
profit = 0;
weight = 0;
copies = 0;
}
Item(int profit, int weight, int copies) {
this->profit = profit;
this->weight = weight;
this->copies = copies;
}
};
static bool cmp(struct Item a, struct Item b) {
double r1 = (double)a.profit / (double)a.weight;
double r2 = (double)b.profit / (double)b.weight;
return r1 > r2;
}
int knap(int W, struct Item arr[], int N) {
sort(arr, arr + N, cmp);
int finalValue = 0;
for (int i = 0; i < N && W > 0; i++) {
while (arr[i].weight <= W && arr[i].copies > 0) {
W -= arr[i].weight;
finalValue += arr[i].profit;
arr[i].copies--;
}
}
return finalValue;
}
int main() {
int w, n;
cin >> w >> n;
Item arr[n]; // Declare an array of Item structs
for (int i = 0; i < n; i++) {
cin >> arr[i].profit >> arr[i].weight >> arr[i].copies;
}
cout << knap(w, arr, n); // Call the knap function with the array
return 0;
}
