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

import java.util.Map;
import java.util.TreeMap;
import java.util.Iterator;
import java.util.Collections;

class sia {

    public static void main(String[] args) {
	Scanner scanner = new Scanner(System.in);
	Integer powierzchnia = scanner.nextInt();
	Integer ilosc_koszen = scanner.nextInt();

	Map<Integer, PolaDlaPredkosci> mapa = new TreeMap<Integer, PolaDlaPredkosci>(Collections.reverseOrder());

	for(int i=0; i < powierzchnia; ++i){
	    Integer predkosc = scanner.nextInt();
	    PolaDlaPredkosci pola = mapa.get(predkosc);

	    if(pola == null){
		pola = new PolaDlaPredkosci(predkosc);
		mapa.put(predkosc, pola);
	    }
	    pola.zwiekszLiczbePol();
	}

	for(int i=0; i < ilosc_koszen; ++i){
	    Long dzien = scanner.nextLong();	    
	    Long wysokosc = scanner.nextLong();

	    System.out.println(wykonajKoszenie(dzien, wysokosc, mapa));
	}
    }

    private static Long wykonajKoszenie(Long dzien, Long wysokosc,
					Map<Integer, PolaDlaPredkosci> mapa) {
	Long skoszonaTrawa = 0L;
	
	Iterator<Integer> it = mapa.keySet().iterator();
	while (it.hasNext()) {
	    Integer klucz = it.next();
	    PolaDlaPredkosci pola =  mapa.get(klucz);
	    Long skoszona = pola.zetnij(wysokosc, dzien);

	    skoszonaTrawa += skoszona;

	    if(skoszona == 0L) {
		break;
	    }
	}
	return skoszonaTrawa;
    }


    static class PolaDlaPredkosci {
	
	private Integer predkosc;
	private Integer iloscPol;
	private Long aktualnaWysokosc;
	private Long ostatnieKoszenie;

	PolaDlaPredkosci(Integer predkosc){
	    this.predkosc = predkosc;
	    this.iloscPol = 0;
	    this.aktualnaWysokosc = 0L;
	    this.ostatnieKoszenie = 0L;
	}

	void zwiekszLiczbePol() {
	    iloscPol ++;
	}

	void rosnij(Long iloscDni){
	    aktualnaWysokosc += iloscDni * predkosc;
	}

	Long zetnij(Long wysokosc, Long dzien) {
	    rosnij(dzien - ostatnieKoszenie);
	    ostatnieKoszenie = dzien;

	    if(aktualnaWysokosc <= wysokosc)
		return 0L;
	    
	    Long wynik = (aktualnaWysokosc - wysokosc) * iloscPol;
	    aktualnaWysokosc = wysokosc;

	    return wynik;
	}
    }
}