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
#include <stdio.h>
#include <algorithm>
#include <vector>
int n,m;
int A[500000+10];
long long B[500000+10];
long long d,b;

struct typ {
  long long d,b;
  int l,r; // [l,r)
  long long cut(){
    return d*A[l]-b;
  }
  long long cut(int L){
    return d*A[L]-b;
  }
};

std::vector<typ> stos;

long long grass(int l,int r,long long d,long long b){
  return d*(B[l]-B[r])-b*(r-l);
}

int search(int l,int p,long long d, long long b)
// szuka elementu v w przedziale [l,p)
{  
  while (l<p) {
    int k = (l+p)/2;
    if (A[k]*d<=b) l=k+1;
    else p=k;
  }
  return l;
}
int q;

int main(){  
  q=scanf("%d%d",&n,&m);
  for(int i=0;i<n;++i) q=scanf("%d",A+i);
  std::sort(A,A+n);
  A[n] = B[n] = 0;
  for(int i=n-1;i>=0;--i) B[i] = B[i+1]+A[i];
  typ x;
  x.d = x.b = 0; x.l=0; x.r = n;
  stos.push_back(x);
  for(int i=0;i<m;++i){
    q=scanf("%lld%lld",&d,&b);
    long long cur = 0;
    typ x ;
    x.d = d; x.b = b; x.l = n; x.r = n;
    while(!stos.empty() && stos.back().cut() < x.cut(stos.back().l)){
      x.l = stos.back().l;
      cur += grass(stos.back().l,stos.back().r,x.d-stos.back().d,x.b-stos.back().b);
      stos.pop_back();
    }
    if (!stos.empty()){
      int j = search(stos.back().l,stos.back().r,x.d-stos.back().d,x.b-stos.back().b);
      if(j < stos.back().r){
        cur += grass(j,stos.back().r,x.d-stos.back().d,x.b-stos.back().b);
        stos.back().r = j;
        x.l = j;
      }
    }
    if (x.l < x.r)  stos.push_back(x);
    printf("%lld\n",cur);
  }
  return 0;
}