#include <bits\\stdc++.h>


using namespace std;
#define pii pair<long long, long long>

long long N, M, lines_read = 0;
queue<pii> sor;

pii next() {
    if (sor.empty()) {
        pii r;
        cin >> r.first >> r.second;
        // cout << "read to main " << r.first << " " << r.second << "\n";
        lines_read++;
        return r;
    }
    pii r = sor.front();
    sor.pop();
    return r;
}

long long count(long long ido) {
    if (lines_read == N) return sor.size();
    pii t;
    cin >> t.first >> t.second;
    // cout << "read to queue " << t.first << " " << t.second << "\n";
    sor.push(t);
    lines_read++;
    while (lines_read <= N && t.first < ido)
    {
        cin >> t.first >> t.second;
        lines_read++;
        sor.push(t);
        // cout << "read to queue " << sor.front().first << " " << sor.front().second << "\n";
    }
    return sor.size();
}

int main() {
    cin >> M >> N;
    priority_queue<pii, vector<pii>, greater<pii>> pultok;
    priority_queue<long long, vector<long long>, greater<long long>> szabad;
    vector<long long> out;
    long long max_count = 0, max_wait = 0;
    for (size_t i = 1; i < M+1; i++)
    {
        pultok.push({0, i});
    }
    for (size_t n = 0; n < N; n++)
    {
        
        pii pali = next();
        // cout << n << ": " << pali.first << " " << pali.second << "\n";
        // // cout << pultok.top().first << " " << pultok.top().second << " " << pali.first << " " << pultok.size() << endl;
        while (!pultok.empty() && pultok.top().first <= pali.first)
        {
            // cout << "sz: " << pultok.top().second << " " << pultok.top().first << "\n";
            szabad.push(pultok.top().second);
            pultok.pop();
        }

        if (!szabad.empty()) {
            // cout << "pult push: " << pali.first + pali.second << " " << szabad.top() << "\n";
            out.push_back(szabad.top());
            pultok.push({pali.first + pali.second, szabad.top()});
            szabad.pop();
        }
        else {
            long long elso = pultok.top().first;
            max_wait = max(max_wait, elso-pali.first);
            max_count = max(max_count, count(elso));
            // cout << "nincs sz\n";
            while (pultok.top().first == elso && !pultok.empty()) 
            {
                // cout << "\tsz push: " << pultok.top().second << " " << pultok.top().first << "\n";
                szabad.push(pultok.top().second);
                pultok.pop();
            }
            // cout << "pultok push: " << elso + pali.second << " " << szabad.top() << "\n";
            pultok.push({elso + pali.second, szabad.top()});
            out.push_back(szabad.top());
            szabad.pop();
        }
    }
    while (pultok.size() > 1) pultok.pop();
    cout << pultok.top().first << " " << max_wait << " " << max_count << "\n"; 
    for (long long x : out) cout << x << "\n";
}