#include <bits/stdc++.h>
#define REP(i, a, n) for(ll i = ((ll) a); i < ((ll) n); i++)
using namespace std;
typedef long long ll;

const ll INF = 1LL << 50;

ll f(ll x, ll A, ll X) {
  return max(A - (x - X) * (x - X), 0LL);
}

ll diff(ll x, ll A, ll X) {
  ll y3 = f(x - 3, A, X), y2 = f(x - 2, A, X), y1 = f(x - 1, A, X), y0 = f(x - 0, A, X);
  ll v2 = y2 - y3, v1 = y1 - y2, v0 = y0 - y1;
  ll a1 = v1 - v2, a0 = v0 - v1;
  return a0 - a1;
}

ll ok(ll k, ll a, ll n, ll *sum) {
  ll l = -INF, r = INF;
  REP(i, 1, n + 1) {
    if(sum[i] < k) {
      ll s = k - sum[i];
      ll x1 = ceil(i - sqrt(a - s));
      ll x2 = floor(i + sqrt(a - s));
      l = max(l, x1);
      r = min(r, x2);
    }
  }
  return l <= r;
}

ll s[3000001];
ll *sum = s + 1000000;

int main(void) {
  ll N, M;
  while(cin >> N >> M, N && M) {
    vector<ll> A(M), X(M - 1);
    REP(i, 0, M - 1) cin >> A[i] >> X[i];
    cin >> A[M - 1];

    REP(i, 0, 3000001) s[i] = 0;
    REP(i, 0, M - 1) {
      ll x1 = X[i] - sqrt(A[i]);
      ll x2 = X[i] + sqrt(A[i]);
      set<ll> candidate;
      REP(k, 0, 5) {
        candidate.insert(x1 + k);
        candidate.insert(x2 + k);
      }
      for(ll x : candidate) {
        sum[x] += diff(x, A[i], X[i]);
      }
    }
    REP(k, 0, 3) REP(i, 0, 3000000) s[i + 1] += s[i];

    ll l = 0, h = INF;
    while(h - l > 1) {
      ll m = (l + h) / 2;
      if(ok(m, A[M - 1], N, sum)) l = m; else h = m;
    }
    cout << l << endl;
  }
}
