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
#include<cstdio>
#include<list>
#include<queue>
#include<algorithm>
#include<utility>

using namespace std;

long long speed[500000];
long long total[500000];

long long t;
bool would_not_touch(long long speed, long long height) {
  long long area_height = speed * t;
  return area_height <= height;
}

int main(void) {
  int cuts;
  int areas;
  scanf("%d %d", &areas, &cuts);

  for (int i = 0; i < areas; i++) {
    scanf("%lld", &speed[i]);
  }
  sort(speed, speed + areas);
  for (int i = 0; i < areas; i++) {
    total[i] = speed[i] + (i == 0 ? 0 : total[i-1]);
  }

  long long cut = 0;
  for (int i = 0; i < cuts; i++) {
    long long day, height;
    scanf("%lld %lld", &day, &height);

    t = day;
    long long* first_cut = lower_bound(speed, speed + areas, height, would_not_touch);
    int cut_idx = first_cut - speed;

    long long to_cut = -cut;
    to_cut += (total[areas-1] - (cut_idx == 0 ? 0 : total[cut_idx-1])) * day;
    to_cut -= (areas - cut_idx) * height;
    to_cut = max(0LL, to_cut);
    cut += to_cut;

    printf("%lld\n", to_cut);
  }

  return 0;
}