#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";
}
}