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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;


public class sia {
	public static void main(final String ... args) throws Exception {
		final BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		String line = in.readLine();
		String[] sizes = line.split(" ");
		long m = Long.parseLong(sizes[1]);
		
		line = in.readLine();
		String[] fieldAsText = line.split(" ");
		long[] growth = new long[fieldAsText.length];
		long[] dayCut = new long[fieldAsText.length];
		long[] cutTo = new long[fieldAsText.length];
		for(int i = 0; i < fieldAsText.length; i++) {
			growth[i] = Long.parseLong(fieldAsText[i]);
		}
		Arrays.sort(growth);
		
		long prevD = 0;
		int cutToIndex = fieldAsText.length;
		for(int j = 0; j < m; j++) {
			line = in.readLine();
			sizes = line.split(" ");
			long d = Long.parseLong(sizes[0]);
			long b = Long.parseLong(sizes[1]);

			
			int cutFromIndex = binarySearch(growth, dayCut, cutTo, d, b + 1);
			
			long sum = 0;
			for(int i = cutFromIndex; i < fieldAsText.length; i++) {
				sum += growth[i] * (d - dayCut[i]) + cutTo[i] - b;
				dayCut[i] = d;
				cutTo[i] = b;
			}
			
			System.out.println(sum);
			
			prevD = d;
		}
		
		in.close();
	}
	
	private static int binarySearch(long[] growth, long[] dayCut, long[] cutTo, long day, long cut) {
		int low = 0;
        int high = growth.length - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            long midVal = growth[mid] * (day - dayCut[mid]) + cutTo[mid];

            if (midVal < cut)
                low = mid + 1;
            else if (midVal > cut)
                high = mid - 1;
            else
                return mid; 
        }
        
        if (low >= growth.length) {
        	return low;
        } else  if (growth[low] * (day - dayCut[low]) + cutTo[low] >= cut) {
        	return low;
        } else {
        	return low + 1;
        }
	}
}