#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<int, vector<int>, greater<int>> szabad_pultok;
    priority_queue<pii, vector<pii>, comp> mukodo_pultok;
    for(int i = 1; i <= m; i++){
        szabad_pultok.push(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 mukodo pultokbol az osszeset, ami elotte vegzett atpakoljuk a szabadba
        while(!mukodo_pultok.empty()){
            ideigl = mukodo_pultok.top();
            if(ideigl.first > erkezes) break;
            szabad_pultok.push(ideigl.second);
            mukodo_pultok.pop();
        }

        // a legkorabban szabadon levo pulthoz megyunk, ha nincs mar szabad pult
        // ha tobb pult szabad, akkor a legkisebbet kene valasztani
        if(szabad_pultok.empty()){
            pult = mukodo_pultok.top();
            mukodo_pultok.pop();
        }
        else{
            pult = {0, szabad_pultok.top()};
            szabad_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});
        }
        mukodo_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";
    }

}