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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
#include <array>
#include <set>

using std::begin;
using std::end;

enum : size_t {
  pos = 0, day = 1, height = 2
 };

typedef unsigned long long length;
typedef unsigned long long days_numeral;
typedef size_t position;
typedef std::tuple<position, days_numeral, length> mowing;
template<typename T_pos, typename T, typename Function>
T value_bsearch(T_pos p, T_pos q, const T value, Function f, const length mowing_day) {
  while(p+1 < q) {
    const T temp = p + (q-p)/2;
    //std::cerr << "f("<<temp <<", " << mowing_day << ") > " << value << '\n';
    if(f(temp, mowing_day) > value) {
      q = temp;
     }
    else {
      p = temp;
     }
   }
  if(f(p, mowing_day) <= value) {
    p += 1;
   }
  return p;
 }

std::set<mowing> history = {mowing(0,0,0)};
std::vector<unsigned long long> pace;
std::vector<unsigned long long> sum;

length find(const position i, const days_numeral mowing_day) {
  auto it = history.upper_bound(std::make_tuple(i, mowing_day, 1000000000001ULL));
  --it;
  if(it == end(history)) {
    return pace[i]*mowing_day;
   }
  auto last_mowing = std::get<day>(*it);
  return std::get<height>(*it) + (mowing_day-last_mowing)*pace[i];
 }

template<typename T>
std::tuple<position, unsigned long long> interval(const position p, T it, const days_numeral mowing_day) {
  const days_numeral last_mowing = std::get<day>(*it);
  const length last_height = std::get<height>(*it);
  ++it;
  days_numeral q;
  if(it == std::end(history)) {
    q = pace.size()-1;
   }
  else {
    q = std::get<pos>(*it)-1;
   }
  typedef std::tuple<position, unsigned long long> return_type;
  return return_type(q-p+1, static_cast<unsigned long long>(mowing_day - last_mowing)*(sum[q] - (p == 0 ? 0 : sum[p-1])) + last_height*static_cast<unsigned long long>(1+q-p));
 }

template<typename T>
std::vector<unsigned long long> prefsum(const T& input) {
  unsigned long long sum = 0;
  std::vector<unsigned long long> result;
  result.reserve(input.size());
  for(auto it = input.cbegin(); it != input.cend(); ++it) {
    sum += *it;
    result.push_back(sum);
   }
  return result;
 }

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);
  unsigned n, m;
  std:: cin >> n >> m;
  pace.reserve(n);
  copy_n(std::istream_iterator<unsigned long long>(std::cin), n,
         std::back_inserter(pace));
  std::sort(begin(pace), end(pace));
  std::vector<std::tuple<days_numeral, length>> schedule(m);
  for(auto& x : schedule) {
    std::cin >> std::get<0>(x) >> std::get<1>(x);
   }
  sum = prefsum(pace);
  for(const auto& mowing_plan : schedule) {
    auto temp = value_bsearch(0U, n, std::get<1>(mowing_plan), find, std::get<0>(mowing_plan));
    const auto begin_temp = temp;
    auto it = history.upper_bound(mowing(temp, 1000000000001, 1000000000001));
    --it;
    unsigned long long answer = 0;
    while(it != std::end(history)) {
      size_t interval_size;
      unsigned long long add_value;
      std::tie(interval_size, add_value) = interval(temp, it, std::get<0>(mowing_plan));
      add_value -= static_cast<unsigned long long>(interval_size) * std::get<1>(mowing_plan);
      answer += add_value;
      if(std::get<pos>(*it) >= begin_temp) {
        it = history.erase(it);
       }
      else {
        ++it;
       }
      if(it != std::end(history)) {
        temp = std::get<pos>(*it);
       }
     }
    std::cout << answer << '\n';
    history.emplace(temp, std::get<0>(mowing_plan), std::get<1>(mowing_plan));
   }
 }