#include <bits/stdc++.h>
#include <functional>
#include <map>
#include <queue>
#include <vector>

using namespace std;

#define pii pair<long long, long long>

struct comp {
    bool operator()(pii a, pii b) {
        if (a.first < b.first) return false;
        if (b.first < a.first) return true;
        return false;
    }
};

long long lines_read = 0;
long long N, M;
vector<long long> pultok;
queue<pii> q;

pii next() {
    if (q.empty()) {
        pii r;
        cin >> r.first >> r.second;
        lines_read++;
        return r;
    }
    pii r = q.front();
    q.pop();
    return r;
}
long long count(long long t) {
    if (lines_read == N) return q.size();
    pii x;
    cin >> x.first >> x.second;
    lines_read++;
    q.push(x);
    while (x.first < t && lines_read < N)
    {
        cin >> x.first >> x.second;
        lines_read++;
        q.push(x);
    }
    return q.size();
}
int  main() {
    cin >> M >> N;
    priority_queue<pii, vector<pii>, comp> pq;
    priority_queue<long long, vector<long long>, greater<long long>> pq2;
    for (size_t i = 1; i < M+1; i++)
    {
        pq.push({0, i});
    }
    long long E, H;
    long long maxvarido = 0;
    long long maxvarakozo = 0;
    for (size_t i = 0; i < N; i++)
    {
        pii temp = next();
        E = temp.first;
        H = temp.second;
        while (pq.top().first <= E && !pq.empty()) {
            pq2.push(pq.top().second);
            pq.pop();
        }
        if (pq2.empty()) {
            long long elso = pq.top().first;
            maxvarido = max(maxvarido, elso-E);
            maxvarakozo = max(count(elso), maxvarakozo);
            while (pq.top().first == elso && !pq.empty()) {
                pq2.push(pq.top().second);
                pq.pop();
            }
            pq.push({elso+H, pq2.top()});
            // cout << i << " " << pq2.top() << endl;
            pultok.push_back(pq2.top());
            pq2.pop();
        }
        else {
            pq.push({E+H, pq2.top()});
            // cout << i << " " << pq2.top() << endl;
            pultok.push_back(pq2.top());
            pq2.pop();
        }
        
    }
    while (pq.size() > 1) pq.pop();
    cout << pq.top().first << " " << maxvarido << " " << maxvarakozo << "\n";
    for (long long& x : pultok) {
        cout << x << "\n";
    }
}