1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
#include<bits/stdc++.h>
#define FOR(i,s,e) for(int i=(s);i<=(e);i++)
#define FORD(i,s,e) for(int i=(s);i>=(e);i--)
#define ALL(k) (k).begin(),(k).end()
#define e1 first 
#define e2 second
#define MP make_pair
#define PB push_back
#define EB emplace_back 
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<int,PII> PIP;
const int MAXN=1000111;
const int MAXK=1000111;

int wyst[MAXN];
int t1[MAXK];
LL tab[MAXN];
LL prs[MAXN];
LL d[MAXN],b[MAXN];

bool chk1(int oi,int pi,int pos){
	LL len=d[oi]-d[pi];
	LL ob=b[pi]+len*tab[pos];
	return ob>b[oi];
}
	

void ustaw(int n){
	int ob=n+1;
	tab[ob]=MAXK;
	FOR(i,1,n) wyst[tab[i]]++;
	int i0=1;
	for(int ii=0;i0<=n;ii++){
		//if(wyst[ii]>0) printf("%d %d\n",ii,wyst[ii]);
		while(wyst[ii]>0) tab[i0]=ii,i0++,wyst[ii]--;
	}
	//FOR(i,1,n) printf("%lld ",tab[i]);
	//puts("");
	
	FORD(i,MAXK-100,1){
		while(ob>=0&&tab[ob]>=i)
			ob--;
		t1[i]=ob+1;
	}
}

main(){
	int n,m;scanf("%d%d",&n,&m);
	FOR(i,1,n) scanf("%lld",&tab[i]);
	ustaw(n);
	
	FOR(i,1,n) prs[i]=prs[i-1]+tab[i];
	//FOR(i,0,15) printf("%d %d\n",i,t1[i]);
	//FOR(i,1,n) printf("%d %lld %lld\n",i,tab[i],prs[i]);
	vector<PII> S;S.emplace_back(1,0);//pos,time
	FOR(i,1,m){
		scanf("%lld%lld",&d[i],&b[i]);
		int pp=n+1;
		LL wynik=0;
		/*puts("\n");
		printf("%d %lld %lld::\n",i,d[i],b[i]);
		for(auto it:S)
			printf("%d %d %lld %lld\n",it.e2,it.e1,d[it.e2],b[it.e2]);
		puts("stos");*/
		int gunwo=0;
		while(!S.empty()){
			int lp=S.back().e1,popw=S.back().e2;
			//printf("\n%d %d;; %d %lld %lld\n",lp,pp,popw,d[popw],b[popw]);
			if(chk1(i,popw,lp)) {
				LL k=b[popw]*(pp-lp)+(d[i]-d[popw])*(prs[pp-1]-prs[lp-1])-b[i]*(pp-lp);
				//printf("A %lld*%d+%lld*%lld-%lld*%d=%lld\n",
				//b[popw],(pp-lp),d[i]-d[popw],prs[pp-1]-prs[lp-1],b[i],pp-lp,k);
				wynik+=k;
				if(S.size()==1) {S[0].e2=i;break;}
				S.pop_back();pp=lp;continue;
			}
			if(d[i]-d[popw]==0) {
				printf("CHOOY %d %d %lld %lld\n",i,popw,d[popw],b[popw]);
				gunwo=1;break;}
			LL valpos=(b[i]-b[popw])/(d[i]-d[popw]);
			if(valpos<=0) valpos=0;
			valpos++;
			//printf("valpos %lld/%lld=%lld;; ",b[i]-b[popw],d[i]-d[popw],valpos);
			if(valpos>=MAXK-110) {
				//puts("pham");
				S.EB(pp,i);
				break;
			}
			int owi=t1[valpos];
			//printf("%d ",owi);
			if(owi<lp) owi=lp;
			if(owi>pp) owi=pp;
			//printf("%d %lld\n",owi,tab[owi]);
			LL k=b[popw]*((LL)(pp-owi))+(d[i]-d[popw])*(prs[pp-1]-prs[owi-1])-b[i]*(
			(LL)(pp-owi));
			//printf("%lld*%d+%lld*%lld-%lld*%d=%lld\n",
			//b[popw],(pp-owi),d[i]-d[popw],prs[pp-1]-prs[owi-1],b[i],pp-owi,k);
			wynik+=k;
			S.EB(owi,i);
			break;
		}
		//printf("%d %lld %lld ",i,d[i],b[i]);
		printf("%lld\n",wynik);
		if(gunwo){puts("NIE");return 0;}
		//if(i!=m) puts("");
	}
}