#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;
    long long vart, vegzett;
    for(int i = 0; i < n; i++){
        cin >> erkezes >> hossz;

        // a legkorabban szabadon levo pulthoz megyunk
        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";
    }

}