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
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

const int N=500005;

long long d, b;
long long sumyA[N+1];//[n] - do n-1 wlacznie
int a[N];

struct Ciach
{
	long long cb, cd;
	int indA;
	bool szukanie;

	Ciach(long long b, long long d, int ind) : cb(b), cd(d), indA(ind), szukanie(false) {}
	Ciach(bool szuk) : cb(0), cd(0), indA(0), szukanie(szuk) {}

	bool operator<(const Ciach &c) const
	{
		if (szukanie)
			return b<c.wys();
		if (c.szukanie)
			return wys()<b;
		return indA<c.indA;
	}

	long long wys() const
	{
		return (d-cd)*a[indA]+cb;
	}
};

int main()
{
	ios_base::sync_with_stdio(false);
	int n, m;
	cin>>n>>m;
	for (int i=0; i<n; ++i)
		cin>>a[i];
	sort(a, a+n);
	for (int i=0; i<n; ++i)
		sumyA[i+1]=sumyA[i]+a[i];

	set<Ciach> ciachy;
	ciachy.insert(Ciach(0, 0, 0));
	Ciach szuk(true);

	for (int i=0; i<m; ++i)
    {
    	cin>>d>>b;
    	long long wyn=0;
    	set<Ciach>::iterator it=ciachy.upper_bound(szuk), it1=it, it2=it;
    	while (it1!=ciachy.end())
    	{
    		const Ciach &c=*it1;
    		++it1;
    		int kon= it1==ciachy.end() ? n : it1->indA;
    		wyn+=(d-c.cd)*(sumyA[kon]-sumyA[c.indA])+(kon-c.indA)*(c.cb-b);
    	}
    	int nowyPocz;
    	if (it==ciachy.begin()) nowyPocz=0;
    	else
    	{
    		int kon= it==ciachy.end() ? n : it->indA;
    		const Ciach &poprz=*--it2;
    		nowyPocz=kon;
    		long long lDni=d-poprz.cd;

    		  int l=poprz.indA, p=kon;
    		  while (l<p)
    		  {
    		    int sr=(l+p)/2;
    		    if (poprz.cb+lDni*a[sr]<=b) l=sr+1;
    		    else p=sr;
    		  }

    			if (l<kon && b<poprz.cb+lDni*a[l])
    			{
    				wyn+=lDni*(sumyA[kon]-sumyA[l])+(kon-l)*(poprz.cb-b);
    				nowyPocz=l;
    			}
    	}
    	ciachy.erase(it, ciachy.end());
    	if (nowyPocz<n)
    		ciachy.insert(Ciach(b, d, nowyPocz));
    	cout<<wyn<<'\n';
    }
	return 0;
}