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
#include <algorithm>
#include <cstdio>
#include <functional>
#include <vector>
using namespace std;
typedef long long i64;

struct Trim
{
  i64 t_,h_;
  int k_;
  
  Trim(i64 t, i64 h, int k) : t_(t), h_(h), k_(k) {}
};

struct Problem
{
  Problem(int n) : n_(n), a_(n), as_(n+1) {}
  
  void prepare();
  inline i64 as(int i, int j) { return as_[j+1] - as_[i]; }
  inline i64 getH(int i, i64 t, const Trim& trim) { return trim.h_ + (t-trim.t_)*a_[i]; }
  inline i64 getSum(int i, int j, i64 t, i64 h, const Trim& trim) { return as(i,j)*(t-trim.t_) + (trim.h_-h)*(j-i+1); }
  int binSearch(int i, int j, i64 t, i64 h, const Trim& trim);
  i64 next(i64 t, i64 h);
  
  int n_;
  vector<int> a_;
  vector<i64> as_;
  vector<Trim> trims_;
};

void Problem::prepare()
{
  sort(a_.begin(), a_.end(), greater<int>());
  for (int i=1; i<=n_; ++i) as_[i] = as_[i-1] + a_[i-1];
  trims_.emplace_back(0,0,n_-1);
}

int Problem::binSearch(int i, int j, i64 t, i64 h, const Trim& trim)
{
  while (i < j)
  {
    int k = (i+j+1)/2;
    if (getH(k,t,trim) > h) i = k;
    else j = k-1;
  }
  return i;
}

i64 Problem::next(i64 t, i64 h)
{
  i64 result = 0;
  int k = -1;
  for (int i=0; i<n_; ++i)
  {
    Trim trim = trims_.back();
    if (getH(i,t,trim) <= h) break;
    int j = trim.k_;
    if (getH(j,t,trim) <= h)
    {
      k = binSearch(i,j,t,h,trim);
      result += getSum(i,k,t,h,trim);
      break;
    }
    trims_.pop_back();
    result += getSum(i,j,t,h,trim);
    i = j;
    k = j;
  }
  if (k != -1) trims_.emplace_back(t,h,k);
  return result;
}

int main()
{
  int n,m;
  scanf("%d%d", &n, &m);
  Problem p(n);
  for (int& x : p.a_) scanf("%d", &x);
  p.prepare();
  for (int i=0; i<m; ++i)
  {
    i64 t,h;
    scanf("%lld%lld", &t, &h);
    printf("%lld\n", p.next(t,h));
  }
}