#include<bits/stdc++.h>

using namespace std;
using ll = long long;

#define rep(i,n) for(int i = 0; i < (n); ++i)
#define reps(i,a,n) for(int i = (a); i < (n); ++i)


ll _a[3000006+2];
ll *a = _a + 1000006;

ll sqrtceir(ll a){
    ll ok = 1000000009;
    ll ng = 0;
    while(ok - ng > 1){
        ll m = (ok + ng)/2;
        if(m * m >= a) ok = m;
        else ng = m;
    }
    return ok;
}

inline void Add(ll x, ll A){
    if(x < 1000006){
        a[x] += A;
    }
}

int main(){
    int n, m;
    while(cin >> n >> m, n){
        memset(_a, 0, sizeof(_a));
        rep(i, m-1){
            ll A, x;
            cin >> A >> x;
            ll R = sqrtceir(A);
            // cout << "#x,r " << x << " " << R << endl;
            {
                ll r = (R*R == A ? R : R-1);
                a[x-r+2] += A;
                a[x-r+1] -= A*2;
                a[x-r+0] += A;
                Add(x+r+3, -A);
                Add(x+r+2, 2*A);
                Add(x+r+1, -A);
            }
            {
                ll r = (R*R == A ? R+1 : R);
                a[x-r+3] -= r*r;
                a[x-r+2] += 2*(r*r-r)-1;
                a[x-r+1] -= (r-1)*(r-1);
                Add(x+r+0, r*r);
                Add(x+r+1, 1-2*(r*r-r));
                Add(x+r+2, (r-1)*(r-1));
            }
        }
        ll A;
        cin >> A;

        // reps(i, 1, n+1) printf("[%2d] %2lld\n", i, a[i]); cout << endl;

        for(int i = 0; i < 3000006; ++i){
            _a[i+1] += _a[i];
        }
        for(int i = 0; i < 3000006; ++i){
            _a[i+1] += _a[i];
        }
        for(int i = 0; i < 3000006; ++i){
            _a[i+1] += _a[i];
        }
        /*
        puts("--------------");
        reps(i, 1, n+1)  printf("[%2d] %2lld\n", i, a[i]); cout << endl;
        */

        ll ok = 0;
        ll ng = 0x1fff'ffff'ffff'ffff;
        while(ng - ok > 1){
            ll m = (ng + ok)/2;
            
            int i = 1;
            for(; i <= n; ++i){
                if(a[i] < m) break;
            }
            if(i <= n && m-a[i] <= A){
                ll OK = i;
                ll NG = i+sqrtceir(A);
                while(NG - OK > 1){
                    ll M = (OK+NG)/2;
                    ll v = a[i] + max(0LL, A-(M-i)*(M-i));
                    if(v >= m) OK = M;
                    else       NG = M;
                }
                //printf("i:%d  X:%lld\n", i, OK);
                ll X = OK;
                for(; i<=n; ++i){
                    ll v = a[i] + max(0LL, A-(X-i)*(X-i));
                    if(v >= m) continue;;
                    if(m-a[i] > A) break;
                    if(i > X) break;
                    ll OK = i;
                    ll NG = i+sqrtceir(A);
                    while(NG - OK > 1){
                        ll M = (OK+NG)/2;
                        ll v = a[i] + max(0LL, A-(M-i)*(M-i));
                        if(v >= m) OK = M;
                        else       NG = M;
                    }
                    //printf("i:%d  X:%lld\n", i, OK);
                    X = OK;
                }
            }

            //printf("Test %lld [%lld, %lld] i:%d => %d\n", m, ok, ng, i, int(i>n));
            if(i > n) ok = m;
            else      ng = m;
        }
        cout << ok << endl;
    }
}






Measured memory_bytes: 26528