#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 1000005
#define SIZE 100005

enum Type{
	R_half,
	L_half,
};

struct Info{
	ll value,loc,left_range,right_range;
};

int N,M;
ll table[2][NUM],final_table[NUM];
ll last_value;
Info info[SIZE];

//最小値tmp_valueのシールドを作れるか調べる
bool is_ok(ll tmp_value){

	ll L = 0,R = N-1;

	ll tmp_left,tmp_right;
	ll left,right,m;

	for(ll i = 0; i < N; i++){
		if(final_table[i] >= tmp_value)continue;
		if(tmp_value-final_table[i] > last_value)return false;

		//自分より左方向の、tmp_valueを達成できる範囲
		left = 0,right = i, m = (left+right)/2;
		while(left <= right){

			if(final_table[i]+last_value-(m-i)*(m-i) >= tmp_value){

				tmp_left = m;
				right = m-1;

			}else{

				left = m+1;
			}
			m = (left+right)/2;
		}
		//自分より右方向の、tmp_valueを達成できる範囲
		left = i,right = N-1,m = (left+right)/2;
		while(left <= right){

			if(final_table[i]+last_value-(m-i)*(m-i) >= tmp_value){

				tmp_right = m;
				left = m+1;

			}else{

				right = m-1;
			}
			m = (left+right)/2;
		}

		L = max(L,tmp_left);
		R = min(R,tmp_right);

		if(L > R)return false;
	}
	return true;
}

void calc(){

	for(int i = 1; i < N; i++){
		table[R_half][i] += table[R_half][i-1];
	}
	for(int i = N-2; i >= 0; i--){
		table[L_half][i] += table[L_half][i+1];
	}
}

bool rangeCheck(int tmp_loc){

	if(tmp_loc >= 0 && tmp_loc <= N-1){
		return true;
	}else{
		return false;
	}
}

void func(){

	ll left,right,m,min_index,max_index;

	for(int i = 0; i < M-1; i++){

		scanf("%lld %lld",&info[i].value,&info[i].loc);
		info[i].loc--;

		//左側
		left = 0,right = info[i].loc,m = (left+right)/2;

		while(left <= right){

			if(info[i].value-(m-info[i].loc)*(m-info[i].loc) >= 0){

				min_index = m;
				right = m-1;

			}else{
				left = m+1;
			}
			m = (left+right)/2;
		}

		info[i].left_range = info[i].loc-min_index;

		//右側
		left = info[i].loc,right = N-1, m = (left+right)/2;

		while(left <= right){

			if(info[i].value-(m-info[i].loc)*(m-info[i].loc) >= 0){

				max_index = m;
				left = m+1;

			}else{
				right = m-1;
			}
			m = (left+right)/2;
		}

		info[i].right_range = max_index-info[i].loc;
	}

	scanf("%lld",&last_value);

	for(int i = 0; i < N; i++){
		table[R_half][i] = 0;
		table[L_half][i] = 0;
	}

	//1回目のimos法[3回差分を足す]
	for(int i = 0; i < M-1; i++){

		for(ll k = 1; k <= 2; k++){
			if(rangeCheck(info[i].loc+k)){
				table[R_half][info[i].loc+k] += -1;
			}
			if(rangeCheck(info[i].loc-k)){
				table[L_half][info[i].loc-k] += -1;
			}
		}

		if(rangeCheck(info[i].loc+info[i].right_range+1)){
			table[R_half][info[i].loc+info[i].right_range+1] += 2;
		}
		if(rangeCheck(info[i].loc-(info[i].left_range+1))){
			table[L_half][info[i].loc-(info[i].left_range+1)] += 2;
		}
	}
	calc();

	//2回目のimos法[2回差分を足す]
	for(int i = 0; i < M-1; i++){

		if(rangeCheck(info[i].loc+info[i].right_range+1)){
			table[R_half][info[i].loc+info[i].right_range+1] += (2*(info[i].right_range-1)+1);
		}
		if(rangeCheck(info[i].loc-(info[i].left_range+1))){
			table[L_half][info[i].loc-(info[i].left_range+1)] += (2*(info[i].left_range-1)+1);
		}
	}
	calc();

	//3回目のimos法
	for(int i = 0; i < M-1; i++){

		if(rangeCheck(info[i].loc+1)){
			table[R_half][info[i].loc+1] += info[i].value;
		}
		if(rangeCheck(info[i].loc-1)){
			table[L_half][info[i].loc-1] += info[i].value;
		}

		if(rangeCheck(info[i].loc+info[i].right_range+1)){
			table[R_half][info[i].loc+info[i].right_range+1] += info[i].right_range*info[i].right_range-info[i].value;
		}
		if(rangeCheck(info[i].loc-(info[i].left_range+1))){
			table[L_half][info[i].loc-(info[i].left_range+1)] += info[i].left_range*info[i].left_range-info[i].value;
		}
	}
	calc();

	ll minimum = BIG_NUM,maximum = -BIG_NUM;

	for(int i = 0; i < N; i++){
		final_table[i] = table[R_half][i]+table[L_half][i];
	}
	for(int i = 0; i < M-1; i++){
		final_table[info[i].loc] += info[i].value;
	}

	for(int i = 0; i < N; i++){
		minimum = min(minimum,final_table[i]);
		maximum = max(maximum,final_table[i]);
	}

	ll L = minimum,R = maximum+last_value,mid = (L+R)/2;
	ll ans = minimum;

	while(L <= R){

		if(is_ok(mid)){

			ans = mid;
			L = mid+1;

		}else{

			R = mid-1;
		}
		mid = (L+R)/2;
	}

	printf("%lld\n",ans);
}

int main(){

	while(true){
		scanf("%d %d",&N,&M);
		if(N == 0 && M == 0)break;

		func();
	}

	return 0;
}



Measured memory_bytes: 29764