Children Holiday

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

ll m, n; vector<ll> ans;

struct Node {
    ll t, z, y;
};

vector<Node> v;

bool good(ll x) {
    ll c = 0;
    for(Node a : v) {
        ll k = a.t*a.z+a.y;
        ll temp = a.z*(x/k)+min(a.z, (x%k)/a.t);
        c += temp;
    }
    return c >= m;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin >> m >> n; v.resize(n); ans.assign(n, 0);
    for(Node& a : v) cin >> a.t >> a.z >> a.y;
    ll l = 0, r = 1e9, opt = 1e9;
    while(l <= r) {
        ll x = l+(r-l)/2;
        if(good(x)) {
            for(int i = 0; i < n; i++) {
                Node a = v[i];
                ll k = a.t*a.z+a.y;
                ll temp = a.z*(x/k)+min(a.z, (x%k)/a.t);
                ans[i] = temp;
            }
            r = x-1; opt = x;
        } else {
            l = x+1;
        }
    }
    cout << opt << "\n";
    for(ll& i : ans) {
        i = min(m, i);
        m -= i;
    }
    for(int i : ans) cout << i << " ";
    return 0;
}