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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class sia {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Siano_ost solver = new Siano_ost();
        solver.solve(1, in, out);
        out.close();
    }

    static class Siano_ost {
        long[] sums;
        Event[] events;
        int events_top;
        int[] A;
        int N;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int M = init(in);
            for (int i = 0; i < M; i++) {
                long currentDay = in.nextLong();
                long height = in.nextLong();
                long max_height = wysokosc(N - 1, currentDay);
                long ans = 0;
                if (max_height >= height) {
                    int nowy_brk_idx = find_brk_idx(height, currentDay);
                    ans = daj_sume(nowy_brk_idx, height, currentDay);
                    events[++events_top] = new Event(nowy_brk_idx, currentDay, height);
                }

                out.println(ans);
            }
        }

        private long daj_sume(int nowy_brk_idx, long height, long currentDay) {
            long ans = 0L;
            int lastIdx = N;
            while (events_top >= 0 && wysokosc(events[events_top].idx, currentDay) >= height) {
                Event ev = events[events_top--];
                if (ev.basis > height) {
                    long szczyt = sum(ev.idx, lastIdx - 1) * (currentDay - ev.when);
                    long podst = (ev.basis - height) * (lastIdx - ev.idx);
                    ans += szczyt + podst;
                } else {
                    long szczyt = sum(ev.idx, lastIdx - 1) * (currentDay - ev.when);
                    long podst = (height - ev.basis) * (lastIdx - ev.idx);
                    ans += szczyt - podst;
                }
                lastIdx = ev.idx;
            }
            ans += reszta(nowy_brk_idx, height, lastIdx, currentDay);

            return ans;
        }

        private long reszta(int nowy_brk_idx, long height, int lastIdx, long currentDay) {
            long a1 = nowy_brk_idx;
            long a2 = lastIdx;
            long b1 = events_top >= 0 ? events[events_top].basis : 0;
            long b2 = height;
            long when = events_top >= 0 ? events[events_top].when : 0;
            long szczyt = sum(nowy_brk_idx, lastIdx - 1) * (currentDay - when);
            long podst = (a2 - a1) * (b2 - b1);
            return szczyt - podst;
        }

        private int find_brk_idx(long height, long currentDay) {
            int lo = -1, hi = N - 1;
            while (lo + 1 < hi) {
                int mid = (lo + hi) >> 1;
                if (wysokosc(mid, currentDay) < height) {
                    lo = mid;
                } else {
                    hi = mid;
                }
            }
            return lo + 1;
        }

        private long wysokosc(int idx, long currentDay) {
            long basis = 0L;
            long when = 0L;
            Event event = find_event(idx);
            if (event != null) {
                basis = event.basis;
                when = event.when;
            }

            return basis + (currentDay - when) * sum(idx, idx);
        }

        private Event find_event(int idx) {
            int lo = 0, hi = events_top + 1;
            while (lo + 1 < hi) {
                int mid = (lo + hi) >> 1;
                if (events[mid].idx <= idx) {
                    lo = mid;
                } else {
                    hi = mid;
                }
            }
            if (events[lo] == null) return null;
            return events[lo].idx <= idx ? events[lo] : null;
        }

        private long sum(int lo, int hi) {
            if (lo > hi) return 0;
            if (lo == 0) return sums[hi];
            return sums[hi] - sums[lo - 1];
        }

        private int init(InputReader in) {
            N = in.nextInt();
            int M = in.nextInt();
            A = new int[N];
            for (int i = 0; i < N; i++) A[i] = in.nextInt();
            Arrays.sort(A);
            sums = new long[N];
            sums[0] = A[0];
            for (int i = 1; i < N; i++) {
                sums[i] = sums[i - 1] + A[i];
            }
            events = new Event[N];
            events_top = -1;
            return M;
        }

        private static class Event {
            private int idx;
            private long when;
            private long basis;

            public Event(int idx, long when, long basis) {
                this.idx = idx;
                this.when = when;
                this.basis = basis;
            }

        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}