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
#include <iostream>

using namespace std;

void funkcja(long long int t[][3], int r){
    int li,lj,smx,smn,z;
    for(li=1; li<r; li++){
        smn=0;
        smx=li;
        z=t[li][0];
        while(smn<smx){
            if(t[li][0]<=t[smn+(smx-smn)/2][0]){
                smx=smn+(smx-smn)/2;
            }
            else{
                smn=smn+(smx-smn)/2+1;
            }
        }
        for(lj=smn; lj<li; lj++){
            t[lj+1][0]=t[lj][0];
        }
        t[smn][0]=z;
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    int n,m,i,j,mx,mn,x;
    cin >>n>>m;
    long long int a[n][3];
    long long int d[n][2],s;
    for (i=0; i<n; i++){
        cin >>a[i][0];
        a[i][1]=0;
        a[i][2]=0;
    }
    for (i=0; i<n; i++){
        cin >>d[i][0]>>d[i][1];
    }
    funkcja(a, n);
    for(i=0; i<m; i++){
        s=0;
        mn=0;
        mx=n-1;
        while(mn<mx){
            x=mn+(mx-mn)/2;
            if(d[i][1]<=a[x][1]+a[x][0]*(d[i][0]-a[x][2])){
                mx=x;
            }
            else{
                mn=x+1;
            }
        }
        for(j=mn; j<n; j++){
            s+=(a[j][1]+a[j][0]*(d[i][0]-a[j][2]))-d[i][1];
            a[j][1]=d[i][1];
            a[j][2]=d[i][0];
        }
        cout <<s<<endl;
    }
    return 0;
}