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
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#define ll long long
#define int long long
using namespace std;

int n, m;
struct ciecie
{
	ll siano;
	ll p, k;
	ll wys, cz;
	ciecie()
	{
		siano = 0;
		p = 0;
		k = 0;
		wys = 0;
		cz = 0;
	}
	ciecie(ll a, ll e, ll b, ll c, ll d)
	{
		siano = d;
		p = b; k = c;
		wys = a;
		cz = e;
	}
};
vector < ciecie > V;
ll v[500005], vs[500005];

ll znajdz_wysokosc(ll miejsce, ll czas)
{
	if (V.size() == 0 || V[0].p > miejsce)
		return czas*v[miejsce];
	int p = 0, k = V.size()-1;
	while(p < k-1)
	{
		int s = (p + k)/2;
		if (V[s].p <= miejsce)
			p = s;
		else
			k = s;
	}
	if (V[V.size()-1].p <= miejsce)
		p = V.size()-1;
	return V[p].wys + v[miejsce] * (czas - V[p].cz);
}

ll znajdz_miejsce_ciecia(ll cz, ll wys)
{
	if (znajdz_wysokosc(1, cz) > wys)
		return 1;
	if (znajdz_wysokosc(n, cz) <= wys)
	{
		//cout<<"B"<<znajdz_wysokosc(n, cz)<<" "<<wys<<endl;
		return -1;
	}
	int p = 1, k = n;
	while(p < k - 1)
	{
		int s = (p+k)/2;
		if (znajdz_wysokosc(s, cz) <= wys)
			p = s;
		else
			k = s;
	}
	return k;
}

ll dodaj_ciecie(ll miejsce, ll cz, ll wys)
{
	ll wynik = 0;
	while(V.size()>0 && V[V.size()-1].k >= miejsce)
	{
		ciecie c = V[V.size()-1];
		V.pop_back();
		ll dl = c.k - max(c.p, miejsce) + 1;
		wynik += c.wys*dl + (vs[c.k] - vs[max(c.p, miejsce)-1]) * (cz - c.cz) - dl * wys;
		if (c.p < miejsce)
		{
			c.k = miejsce - 1;
			V.push_back(c);
		}
	} 	
	V.push_back( ciecie(wys, cz, miejsce, n, wynik));
	return wynik;
}

void wypisz_vector()
{
	for(int i=0; i<V.size(); i++)
	{
		cout << V[i].cz<<" "<<V[i].wys<<" "<<V[i].p<<" "<<V[i].k<<endl;
	}
}

main()
{
	scanf("%lld%lld", &n, &m);
	V.push_back(ciecie(0, 0, 1, n, 0));
	for(int i=1; i<=n; i++)
		scanf("%lld", &v[i]);
	sort(v+1, v+n+1);
	for(int i=1; i<=n; i++)	
		vs[i] = vs[i-1] + v[i];
	
	ll cz, wys;
	while(m--)
	{
		scanf("%lld%lld", &cz, &wys);
		ll miejsce = znajdz_miejsce_ciecia(cz, wys);
		//cout<<"A"<<miejsce<<"A";
		if (miejsce != -1)
			printf("%lld\n", dodaj_ciecie(miejsce, cz, wys));
		else
			printf("0\n");
		//wypisz_vector();
	}

	return 0;
}