12321 - Gas Stations

//12321 - Gas Stations
//Karikó Csongor
#include <iostream>
#include <algorithm>
#define MAX_G 10010
using namespace std;

int L, G, a, b;
struct range{
    int x, y;

    range(int _x, int _y) { x = _x;
        y = _y;
    }

    range(){}
};

bool cmp (const range& left, const range& right){
    if (left.x == right.x) return left.y > right.y;
    return left.x < right.x;
}

range ranges[MAX_G];

int main(){
    cin >> L >> G;
    do{
        for (int i = 0; i < G; ++i){
            cin >> a >> b;
            ranges[i].x = a - b;
            ranges[i].y = a + b;
        }

        sort(ranges, ranges + G, cmp);

        int maxLen = 0;
        int newMaxLen = 0;
        int deleted = 0;
        for (int i = 0; i < G; ++i) {
            while(ranges[i].x <= maxLen && i < G){
                //cout << "try " << ranges[i].x << " - " << ranges[i].y << '\n';
                newMaxLen = max(newMaxLen, ranges[i].y);
                ++i;
            }

            deleted++;

            if (newMaxLen >= L) break;

            if (newMaxLen == maxLen && maxLen < L) {
                // no solution
                //cout << "maxLen: " << maxLen << '\n';
                deleted = -1;
                break;
            } else
                --i;

            //cout << "found\n";

            maxLen = newMaxLen;

        }

        if (deleted == -1 || newMaxLen < L) cout << "-1\n";
        else
        cout << G - deleted << '\n';

        cin >> L >> G;
    } while (L > 0);

    return 0;
}