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
#include <stdio.h>

/* dumb O(n*m) solution */
struct {
    long long a, b;
} t[500000];

int main() {
    int n, m, i, j;
    long long pd=0, nd, d, b, s;
    scanf("%d %d", &n, &m);
    for(i=0; i<n; ++i) {
        scanf("%lld", &t[i].a);
        t[i].b=0;
    }
    for(j=0; j<m; ++j) {
        scanf("%lld %lld", &d, &b);
        nd=d-pd;
        pd=d;
        s=0;
        for(i=0; i<n; ++i) {
            if((t[i].b+=nd*t[i].a)>b) {
                s+=t[i].b-b;
                t[i].b=b;
            }
        }
        printf("%lld\n", s);
    }
    return 0;
}