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
// Author: Kamil Nizinski
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstring>
#include <math.h>
#define debug(fmt,...) //fprintf(stderr,fmt, ## __VA_ARGS__)
#define mp make_pair
#define ft first
#define sd second
#define psb push_back
#define ppb pop_back
using namespace std;
typedef long long int ll;
typedef long long unsigned llu;
typedef double dd;
const int MAXN=500007;
int A[MAXN],n,m,C[1000007],TC[1000007],maxA=0;
ll TA[1000007];
stack < pair < pair < ll, ll > , int > > S;
int main()
{
  int i,j,a,pa,upp;
  ll d,b,ans,pd,pb;
  scanf("%d%d",&n,&m);
  for(i=0;i<n;i++) {
    scanf("%d",&A[i]);
    maxA=max(maxA,A[i]);
    C[A[i]]++;
  }
  i=0;
  /*for(a=1;a<=maxA;a++) {
    for(j=0;j<C[a];j++) {
      A[i]=a;
      i++;
    }
  }*/
  for(a=maxA;a>=0;a--) {
    TA[a]=TA[a+1]+1ll*C[a]*a;
    TC[a]=TC[a+1]+C[a];
  }
  /*debug("TA: ");
  for(a=1;a<=maxA+1;a++) {
    debug("%lld ",TA[a]);
  }
  debug("\n");
  debug("TC: ");
  for(a=1;a<=maxA+1;a++) {
    debug("%d ",TC[a]);
  }
  debug("\n");*/
  S.push(mp(mp(0ll,0ll),1));
  while(m--) {
    scanf("%lld%lld",&d,&b);
    ans=0ll;
    upp=maxA+1;
    while(!S.empty()) {
      pd=S.top().ft.ft;
      pb=S.top().ft.sd;
      pa=S.top().sd;
      a=(int)(b-pb)/(d-pd)+1;
//       debug("a=%d\n",a);
//       debug("pd=%lld\npb=%lld\npa=%d\n",pd,pb,pa);
      if(pa>=a) {
        ans+=1ll*pb*(TC[pa]-TC[upp])+1ll*(TA[pa]-TA[upp])*(d-pd)-1ll*b*(TC[pa]-TC[upp]);
        S.pop();
        upp=pa;
      }
      else {
        a=min(a,upp);
        ans+=1ll*pb*(TC[a]-TC[upp])+1ll*(TA[a]-TA[upp])*(d-pd)-1ll*b*(TC[a]-TC[upp]);
        break;
      }
//       debug("ans=%lld\n",ans);
    }
    if(ans>0ll) S.push(mp(mp(d,b),max(a,1)));
    printf("%lld\n",ans);
  }
  return 0;
}