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
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long LL;
const int N=500*1000+7;

LL rate[N];
LL pref[N];

struct interval
{
  int beg;
  int end;
  LL h;
  LL day_d;
} intr[N];
int intr_c=0;

inline LL intr_cost (int beg, int end, LL days, LL current_h, LL desired_h)
{
  return (pref[end]-pref[beg-1])*days+LL(end-beg+1)*(current_h-desired_h);
}

int main ()
{
	int n, m;
  scanf ("%d%d", &n, &m);
  for (int i=1; i<=n; i++)
    scanf("%lld", &rate[i]);
  sort(rate+1, rate+n+1);
  for (int i=1; i<=n; i++)
    pref[i]=pref[i-1]+rate[i];

  intr[intr_c++]={1,n,0,0};

  LL last_day=0;

  for (int i=0; i<m; i++)
  {
    LL current_day, height;
    scanf("%lld%lld", &current_day, &height);
    intr[intr_c-1].day_d += current_day-last_day;
    last_day = current_day;

    LL days = 0;
    LL wyn = 0;
    while (intr_c!=0)
    {
      interval& cur = intr[intr_c-1];
      days+=cur.day_d;
      if (days*rate[cur.beg]+cur.h >= height)
      {
        wyn += intr_cost(cur.beg, cur.end, days, cur.h, height);
        intr_c--;
      }
      else
        break;
    }

    if (intr_c == 0)
    {
      intr[intr_c++] = {1, n, height, 0};
    }
    else
    {
      interval& cur = intr[intr_c-1];

      int pivot;
      if (days*rate[cur.end]+cur.h < height)
        pivot = cur.end;
      else
      {
        int p = cur.beg, k = cur.end, mid;
        while (k-p>1)
        {
          mid = (p+k)/2;
          if (days*rate[mid]+cur.h >= height)
            k = mid;
          else
            p = mid;
        }
        pivot = p;
      }

      wyn += intr_cost(pivot+1, cur.end, days, cur.h, height);
      cur.end = pivot;
      cur.day_d = days;

      if (pivot != n)
        intr[intr_c++] = {pivot+1, n, height, 0};
    }

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

	return 0;
}