#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
template <typename T> struct ImosNijikansu {
    int n;
    vector<T> v;
    vector<pair<int, T>> pre, prepre;
    ImosNijikansu(int n) { init(n); } ImosNijikansu() {}
    void init(int _n) { n = _n; v.resize(n, 0); pre.clear(), prepre.clear(); }
    void set(int l, int r) {
        v[l] += 1;
        if(l + 1 < n) v[l + 1] += 1;
        if (r < n) v[r] -= 2;

        prepre.push_back({ r, -(r-l)*2+1 });
        pre.push_back({ r, -1LL*(1 + 2 * (r-l) - 1)*(r-l)/2 });
    }
    void build() {
        rep(i, 1, v.size()) v[i] += v[i - 1];
        fore(p, prepre) if(p.first < n) v[p.first] += p.second;
        rep(i, 1, v.size()) v[i] += v[i - 1];
        fore(p, pre) if (p.first < n) v[p.first] += p.second;
        rep(i, 1, v.size()) v[i] += v[i - 1];
    }
    T operator[](int i) { return v[i]; }
    void dump() {
        cout << "dump : [";
        for (T i : v) cout << "\t" << i;
        cout << " ]" << endl;
    }
};
template <typename T> struct ImosNijikansuSpread {
    int n;
    vector<T> v;
    ImosNijikansu<T> imos1, imos2;
    vector<int> sub;
    ImosNijikansuSpread(int n) { init(n); } ImosNijikansuSpread() {}
    void init(int _n) { n = _n; v.resize(n); imos1.init(n); imos2.init(n); sub.clear(); }
    void set_start1(int cent, int len) { // from 1 to len^2
        imos1.set(cent, cent + len);
        imos2.set(n - 1 - cent, n - 1 - cent + len);
        sub.push_back(cent);
    }
    void set_start0(int cent, int len) { // from 0 to len^2
        if(cent + 1 < n) imos1.set(cent + 1, cent + 1 + len);
        if (n - 1 - cent + 1 < n) imos2.set(n - 1 - cent + 1, n - 1 - cent + 1 + len);
    }
    void build() {
        imos1.build();
        imos2.build();

        rep(i, 0, n) v[i] += imos1[i];
        rep(i, 0, n) v[i] += imos2[n - 1 - i];
        fore(i, sub) v[i]--;
    }
    T operator[](int i) { return v[i]; }
    void dump() {
        cout << "dump : [";
        for (T i : v) cout << "\t" << i;
        cout << " ]" << endl;
    }
};
template <typename T> struct Imos {
    vector<T> v; Imos(int n) { init(n); } Imos() {} void init(int n) { v.resize(n, 0); }
    void set(int l, int r, T x) { if (l < 0) l = 0; v[l] += x; if (r < v.size()) v[r] -= x; } // [l,r)に+x
    void build() { rep(i, 1, v.size()) v[i] += v[i - 1]; } T operator[](int i) { return v[i]; }
    void dump() {cout << "dump : [";for (T i : v) cout << " " << i;cout << " ]" << endl;}};
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/




int N, M, A[101010], X[101010], AM;
ll v[1010101];
ll w[1010101];
//---------------------------------------------------------------------------------------------------
int check(ll mi) {
    rep(i, 0, N) w[i] = 0;
    rep(i, 0, N) {
        if (v[i] + AM < mi) return 0;

        int ok = 0, ng = N;
        while (ok + 1 != ng) {
            int md = (ok + ng) / 2;
            if (mi <= v[i] + max(0LL, AM - 1LL * md * md)) ok = md;
            else ng = md;
        }

        int L = max(0, i - ok);
        int R = min(N, i + ok + 1);
        w[L]++;
        if (R < N) w[R]--;
    }
    rep(i, 1, N) w[i] += w[i - 1];
    rep(i, 0, N) if (w[i] == N) return 1;
    return 0;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    while (cin >> N >> M) {
        if (N == 0) return;
        rep(i, 0, M - 1) cin >> A[i] >> X[i];
        cin >> AM;

        Imos<ll> imos(N);
        ImosNijikansuSpread<ll> imos2(N);

        rep(i, 0, M - 1) {
            X[i]--;

            int ok = 1, ng = 101010;
            while (ok + 1 != ng) {
                int md = (ok + ng) / 2;
                if (1LL * md*md <= A[i]) ok = md;
                else ng = md;
            }

            imos.set(X[i] - ok, X[i] + ok + 1, A[i]);
            imos2.set_start0(X[i], ok);
        }

        imos.build();
        imos2.build();
        rep(i, 0, N) v[i] = imos[i] - imos2[i];

        //rep(i, 0, N) printf("%lld ", v[i]); printf("\n");

        ll ok = 0, ng = infl;
        while (ok + 1 != ng) {
            ll md = (ok + ng) / 2;
            if (check(md)) ok = md;
            else ng = md;
        }
        printf("%lld\n", ok);
    }
}



Measured memory_bytes: 61456