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
#include<iostream>
using namespace std;
long long n,m,wzrosty[1000003],pom,trawa[1000003],dzien,dlugosc,roznica,a,w;
void sortuj(long long T[],long long lewy,long long prawy)
{
long long i=lewy,j=prawy;
long long srodek=T[(lewy+prawy)/2],pom;
do
{
while(T[i]<srodek)i++;
while(T[j]>srodek)j--;
if(i<=j)
{
pom=T[i]	;
T[i]=T[j];
T[j]=pom;
i++;
j--;	
}
}
while(i<=j)	;
if(lewy<j) sortuj(T,lewy,j);
if(prawy>i) sortuj(T,i,prawy);
		
}


long long szukaj(long long l,long long p,long long dl)
{
long long srodek=(l+p)/2;


if(l==p)
return l;




if(trawa[srodek]<=dl)
szukaj(srodek+1,p,dl);
else
szukaj(l,srodek,dl);
	
	
	
	
	
	
	
	
	
	
}







main()
{pom=1;
cin>>n>>m;	
for(int k=1;k<=n;k++)
cin>>wzrosty[k];
sortuj(wzrosty,1,n);
for(int k=1;k<=n;k++)	
trawa[k]=wzrosty[k];	
for(int k=1;k<=m;k++)
{
	cin>>dzien>>dlugosc;
w=0;	
roznica=dzien-pom;
pom=dzien;	
	
for(long long j=1;j<=n;j++)
trawa[j]+=roznica*wzrosty[j];

if(dlugosc<trawa[n])
a=szukaj(1,n,dlugosc);
else
a=n+1;
	
for(long long j=a;j<=n;j++)
{
w+=trawa[j]-dlugosc;
trawa[j]=dlugosc;	
	
	
	
}



	
cout<<w<<endl;	
}	
	
return 0;	
	
}