#include <bits/stdc++.h>

//#define DEBUG_OUTPUT

#ifndef BITSET_IMPL
#define BITSET_IMPL bitpq
#endif

using namespace std;

class bitpq {
    
    private:
        size_t n;
        priority_queue<int, vector<int>, greater<int>> q;
        
        
    public:
        
        void resize(size_t _n) {
            this->n = _n;
            
            
            for (size_t i = 0; i < n; i++)
                q.emplace(i);
        }
        
        bool is_any_set(void) const {
            return q.size() > 0;
        }
        
        int reset_first_set(void) {
            assert(is_any_set());
            
            int idx = q.top(); q.pop();
            
            return idx;
        }
        
        
        void set_bit(int idx) {
            assert(0 <= idx && idx < (int)n);
            q.emplace(idx);
        }

};

template<typename bit_container_type>
class Task {
    private:
        struct customer {
            int id, arrival, time_needed;
            int server_id;
            
            customer(int x, int y, int z) : id(x), arrival(y), time_needed(z) {}
        };
        
        size_t n, m;
        vector<customer> c; // customers
        bit_container_type b;
        
        uint64_t last_time = 0, max_wait_cnt = 0, max_wait_time = 0;

    public:
        static constexpr int MAXE = 1000000000;
        static constexpr int MAXH = 1000000000;
        
        void input(void) {
            
            ios_base::sync_with_stdio(false);
            cin.tie(nullptr);
            
            cin >> m >> n;
            
            c.reserve(n);
            b.resize(m);
            
            for (size_t i = 0; i < n; i++) {
                int x, y;
                cin >> x >> y;
                
                assert(1 <= x && x <= MAXE);
                assert(1 <= y && y <= MAXH);
                
                c.emplace_back(i+1, x, y);
            }
            
            assert(is_sorted(begin(c), end(c), [](const auto & a, const auto & b) -> bool {
                return a.arrival < b.arrival;
            }));
        }
        
        
        void solve(void) {
            priority_queue<pair<uint64_t, int>, vector<pair<uint64_t, int>>, greater<pair<uint64_t, int>>> q;
            
            uint64_t time = 1;
            size_t cid = 0, next_arrives = 0;
            
            while (cid < n || !q.empty()) {

#ifdef DEBUG_OUTPUT
                printf("at time = %" PRIu64 "\n", time);
#endif

                while (!q.empty() && q.top().first <= time) {
                    auto cst = q.top(); q.pop();
                    b.set_bit(c[cst.second].server_id);
                        
                    last_time = max(last_time, cst.first);
#ifdef DEBUG_OUTPUT
                    printf("\tcustomer #%d left from server %d\n", c[cst.second].id, c[cst.second].server_id+1);
#endif
                }
                   
                while (b.is_any_set() && cid < n && (uint64_t)c[cid].arrival <= time) {
                    
                    c[cid].server_id = b.reset_first_set();
                    assert(c[cid].server_id >= 0);
                        
                    q.emplace(time + c[cid].time_needed, cid);
                    // pair of two integers:
                    //   - the first moment in time this customer will have left the building
                    //   - customer id (index in Task::c vector)
#ifdef DEBUG_OUTPUT
                    printf("\tcustomer #%d arrived at %d, went to server %d after waiting for %" PRIu64 " time\n", c[cid].id, c[cid].arrival, c[cid].server_id+1, time - c[cid].arrival);
#endif
                    max_wait_time = max(max_wait_time, time - c[cid].arrival);
                        
                    cid += 1;
                }
                
                uint64_t next_time = numeric_limits<uint64_t>::max();
                
                if (!q.empty()) {
                    next_time = q.top().first;
                }
                    
                if (b.is_any_set() && cid < n) {
                    next_time = min(next_time, (uint64_t)c[cid].arrival);
                }
                
                if (next_time != numeric_limits<uint64_t>::max()) {
                
                    while (next_arrives < n && (uint64_t)c[next_arrives].arrival < next_time)
                        next_arrives += 1;    
                        
                    max_wait_cnt = max(max_wait_cnt, (uint64_t)next_arrives - cid);
                    
                }
                    
                time = next_time;
            }
        }
        
        void output(void) {
#ifdef DEBUG_OUTPUT
            fflush(stdout);
#endif

            cout.tie(nullptr);
            
            cout << last_time << ' ' << max_wait_time << ' ' << max_wait_cnt << '\n';
            
            for (auto & x : c)
                cout << x.server_id+1 << '\n';
        }
};



int main() {

    Task<BITSET_IMPL> t;

    t.input();
    t.solve();
    t.output();

    return 0;
}