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
import java.util.Arrays;
import java.util.Scanner;

/**
 * Created by lpalonek on 29/09/15.
 */
class sia {
    public static void main(String args[]) {
        Scanner keyboard = new Scanner(System.in);
        int area = keyboard.nextInt();
        int mowNumber = keyboard.nextInt();
        long[] growthRate = new long[area];
        long growth = 0;
        long growthMin = -1;
        for (int i = 0; i < area; i++) {
            growthRate[i] = keyboard.nextLong();
            growth += growthRate[i];
            if (growthMin > growthRate[i] || growthMin < 0) {
                growthMin = growthRate[i];
            }
        }
        Arrays.sort(growthRate);
        long prevDay = 0;
        long prevMowingHeight = 0;
        long sum = 0;
        long diff = 0;
        for (int i = 0; i < mowNumber; i++) {
            long day = keyboard.nextLong();
            long mowingHeight = keyboard.nextLong();
//            long sum = 0;
            long growFactor = mowingHeight - prevMowingHeight;
//            long growFactor = Math.abs(mowingHeight - prevMowingHeight);
            long dayFactor = day - prevDay;
            if (growFactor < 0) {
                growFactor = mowingHeight;
                sum = dayFactor * growth - growFactor * area + prevMowingHeight * area;
            } else {
                sum = dayFactor * growth - growFactor * area;
            }

            if (growthMin * dayFactor < growFactor && (growFactor != mowingHeight || prevMowingHeight == 0)) {
                int index = Arrays.binarySearch(growthRate, growFactor / dayFactor);
                if (index < 0) {
                    index = index * (-1) - 1;
                } else {
                    index++;
                }
                if (index != growthRate.length && growthRate[index] == growthRate[index + 1]) {
                    while (index != growthRate.length && growthRate[index] == growthRate[index + 1]) {
                        ++index;
                    }
                    ++index;
                } else {
                    if (index != growthRate.length && growthRate[index] != growthRate[index + 1]) {
                        index++;
                    }
                }

                for (int j = 0; j < index; j++) {
                    diff += growFactor - growthRate[j] * dayFactor;
                }
                sum += diff;
            } else {
                sum -= diff;
                diff = 0;
            }
//
            prevDay = day;
            prevMowingHeight = mowingHeight;
            System.out.println(sum);
        }
    }
}