#include <bits/stdc++.h> using namespace std; #define int long long signed main() { int sumka , m; cin >> sumka >> m; vector <pair<double , int>> cmb; vector <pair<double , int>> multp; for(int i = 0 ; i < m ; i++){ int cost , weight , combo; cin >> cost >> weight >> combo; double h = cost / double(weight); cmb.push_back({h , combo}); multp.push_back({h , weight}); } sort(cmb.rbegin() , cmb.rend()); sort(multp.rbegin() , multp.rend()); int sum = sumka; int ans = 0; for(int i = 0 ; i < m ; i++){ for(int j = 0 ; j < cmb[i].second ; j++){ if(multp[i].second <= sum){ sum -= multp[i].second; ans += multp[i].second * multp[i].first; } } } cout << ans << endl; }