#include <bits/stdc++.h>

using namespace std;

typedef pair<long long, int> pii;

struct comp{
    bool operator()(pii a, pii b){
        if(a.first == b.first) return a.second > b.second;
        return a.first > b.first;
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int m, n;
    cin >> m >> n;
    // egy priority_queueban taroljuk a pultokat
    // {elso szabad idopont, pult szama}
    priority_queue<pii, vector<pii>, comp> pultok;
    for(int i = 1; i <= m; i++){
        pultok.push({0, i});
    }

    long long nap_vege = 0;
    long long legtobb_varas = 0;
    vector<int> kiszolgalo_pult(n);
    // {idopont, nyit vagy zar}
    vector<pii> varakozok;

    long long erkezes, hossz;
    pii pult, ideigl;
    int legkozelebb;
    long long pult_ido;
    long long vart, vegzett;
    for(int i = 0; i < n; i++){
        cin >> erkezes >> hossz;

        // a legkorabban szabadon levo pulthoz megyunk
        // ha tobb pult szabad, akkor a legkisebbet kene valasztani
        pult_ido = pultok.top().first;
        // osszes olyan pultot, ami az erkezesig van meg kell vizsgalni
        // lehetne optimalisabban is, ha kulon eltarolnank az erkezes elott szabad pultokat
        // de remelem igy is atmegy
        if(pult_ido <= erkezes){
            vector<pii> szabadok;
            int legjobb = 1e9;
            while(!pultok.empty()){
                ideigl = pultok.top();
                if(ideigl.first > erkezes) break;
                pultok.pop();
                szabadok.push_back(ideigl);
                legjobb = min(legjobb, ideigl.second);
            }
            for(auto akt : szabadok){
                if(akt.second == legjobb){
                    pult = akt;
                }
                else{
                    pultok.push(akt);
                }
            }
        }
        else{
            pult = pultok.top();
            pultok.pop();
        }


        vart = max((long long)0, pult.first-erkezes);
        vegzett = erkezes + vart + hossz;

        nap_vege = max(nap_vege, vegzett);
        legtobb_varas = max(legtobb_varas, vart);
        kiszolgalo_pult[i] = pult.second;

        if(vart > 0){
            varakozok.push_back({erkezes, 1});
            varakozok.push_back({erkezes+vart, -1});
        }
        pultok.push({vegzett, pult.second});
    }

    int legtobben_egyszerre_varok = 0;
    sort(varakozok.begin(), varakozok.end());
    varakozok.push_back({-1, -1});
    int epp_varnak = 0;
    for(int i = 0; i < varakozok.size()-1; i++){
        epp_varnak += varakozok[i].second;
        if(varakozok[i].first != varakozok[i+1].first){
            legtobben_egyszerre_varok = max(legtobben_egyszerre_varok, epp_varnak);
        }
    }


    cout << nap_vege << " " << legtobb_varas << " " << legtobben_egyszerre_varok << "\n";
    for(int x : kiszolgalo_pult){
        cout << x << "\n";
    }

}