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
#include <cstdio>
#include <algorithm>
#include <vector>
#define FOR(x, n) for(int x = 0, __n = (n); x < __n; x++)
#define FORI(x, a, n) for(int x = (a), __n = (n); x < __n; x++)
#define FORR(x, n) for(int x = (n)-1; x >= 0; x--)

using namespace std;
#define MAXN 500001
#define MAXV 1001

#define var long long


int n;
var a[MAXN];
var tot[MAXN];

var range(int from, int to) {
  var res = tot[from];
  if(to < n) res -= tot[to];
  return res;
}

struct T {
  int from, to;
  var b, last;
  T(int from, int to, var b, var last):from(from), to(to), b(b), last(last) {}
  
  var heightAt(int p, var day) {
    // if(p<from || p>=to) fprintf(stderr, "ERR\n");
    return b + a[p] * (day - last);
  }
  
  var cutoffPos(var h, var day) {
    int a = from, b = to;
    
    while(b > a) {
      int c = (a+b)/2;
      
      if(heightAt(c, day) >= h) {
        b = c;
      } else {
        a = c+1;
      }
    }
    return a;
  }
  
  var cutoffValue(int p, var h, var day) {
    // if(heightAt(p, day) < h) fprintf(stderr, "ERR2\n");
    // printf("(%d, %d), %lld, %lld, %lld, %lld\n", p, to, range(p, to), (day-last), (to-p), (h-b));
    return range(p, to)*(day-last) - (to-p)*(h-b);
  }
  
  var cutoff(int pos, var h, var day) {
    to = pos;
    
    return to > from;
  }
};

main() {
  int  m; scanf("%d%d", &n, &m);
  FOR(i, n) scanf("%lld", a + i);
  
  sort(a, a+n); 
  
  for(var rest=0, i = n-1; i>=0; i--) {
    rest = (tot[i] = rest + a[i]);
  }
  // FOR(i, n) printf(">%lld\n", tot[i]);
  vector<T> V;
  V.push_back(T(0,n,0,0));
  
  FOR(i, m) {
    var day, b; scanf("%lld%lld", &day, &b);
    var pos;
    var val = 0;
    // FOR(i, n) printf("%lld ", V.back().heightAt(i, day));
    // FOR(i, V.size()) {
    //   printf("#(%d,%d)\n", V[i].from, V[i].to);
    // }
    // printf("\n");
    while(!V.empty()) {
      pos = V.back().cutoffPos(b, day);
      val += V.back().cutoffValue(pos, b, day);
      // printf("cut: pos:%lld, val:%lld\n", pos, val);
      if(!V.back().cutoff(pos, b, day)) {
        V.pop_back();
      } else {
        break;          
      }
    }
    
    V.push_back(T(pos, n, b, day));
    printf("%lld\n", val);
  }
}