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
// tested by Hightail: https://github.com/dj3500/hightail
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <stack>
#include <cstring>
#include <iomanip>
#include <ctime>
#include <cassert>
using namespace std;
#define pb push_back
#define INF 1001001001
#define FOR(i,n) for(int (i)=0;(i)<(n);++(i))
#define FORI(i,n) for(int (i)=1;(i)<=(n);++(i))
#define mp make_pair
#define pii pair<int,int>
#define ll long long
#define vi vector<int>
#define SZ(x) ((int)((x).size()))
#define fi first
#define se second
#define wez(n) int (n); scanf("%d",&(n));
#define wez2(n,m) int (n),(m); scanf("%d %d",&(n),&(m));
#define wez3(n,m,k) int (n),(m),(k); scanf("%d %d %d",&(n),&(m),&(k));
inline void pisz(int n) { printf("%d\n",n); }
template<typename T,typename TT> ostream& operator<<(ostream &s,pair<T,TT> t) {return s<<"("<<t.first<<","<<t.second<<")";}
template<typename T> ostream& operator<<(ostream &s,vector<T> t){FOR(i,SZ(t))s<<t[i]<<" ";return s; }
#define DBG(vari) cout<<"["<<__LINE__<<"] "<<#vari<<" = "<<(vari)<<endl;
#define ALL(t) t.begin(),t.end()
#define FOREACH(i,t) for (__typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
#define TESTS wez(testow)while(testow--)
#define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
#define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i)
#define REMAX(a,b) (a)=max((a),(b));
#define REMIN(a,b) (a)=min((a),(b));
#define IOS ios_base::sync_with_stdio(0);

const int N = 500007;
ll a[N], prefsum[N];

struct S {
   int l, r;
   ll d, b;
};

int main () {
   wez2(n,m);
   FORI(i,n) scanf("%lld", a+i);
   sort(a+1, a+n+1);
   FORI(i,n) prefsum[i] = prefsum[i-1] + a[i];
   vector<S> q = {{1,n,0,0}};
   while (m--) {
      ll dnow, bnow;
      scanf("%lld %lld", &dnow, &bnow);
      ll res = 0;
      while (!q.empty()) {
         S s = q.back();
         if (bnow <= s.b + a[s.l] * (dnow - s.d)) {
            // cale do sciecia
            res += (s.b - bnow) * (s.r - s.l + 1) + (prefsum[s.r] - prefsum[s.l-1]) * (dnow - s.d);
            q.pop_back();
         } else if (bnow <= s.b + a[s.r] * (dnow - s.d)) {
            // czesc do sciecia
            int mini = s.r, from = s.l + 1, to = s.r - 1;
            while (from <= to) {
               int mid = (from + to) / 2;
               if (bnow <= s.b + a[mid] * (dnow - s.d)) {
                  mini = mid;
                  to = mid - 1;
               } else {
                  from = mid + 1;
               }
            }
            // s.l ... mini-1 nie do sciecia, mini ... s.r do sciecia
            q.pop_back();
            q.pb({s.l, mini-1, s.d, s.b});
            q.pb({mini, s.r, s.d, s.b});
         } else {
            // nic do sciecia
            break;
         }
      }

      int l = q.empty() ? 1 : q.back().r + 1;
      if (l <= n) q.pb({l, n, dnow, bnow});
      printf("%lld\n", res);
   }
}