#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>

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

int lines_read = 0;
int N, M;
vector<int> pultok;
queue<pii> q2;

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