Se citesc n job-uri, fiecare avand un deadline si un profit; fiecare job dureaza exact 1 unitate de timp, iar o singura masina este disponibila. Determinati, folosind metoda Greedy, profitul maxim total obtinut executand un subset de job-uri, fiecare inainte de (sau exact la) deadline-ul sau.
- Date de intrare
- Pe prima linie se citeste n. Urmeaza n linii, fiecare cu doua numere: deadline-ul si profitul unui job.
- Date de iesire
- Se afiseaza un singur numar: profitul maxim total.
- Restrictii
- 1 <= n <= 1000, 1 <= deadline <= 1000, 0 <= profit <= 10^6
Exemple
Exemplul 1
Intrare
4 4 20 1 10 1 40 1 30
Iesire
60
Exemplul 2
Intrare
5 2 100 1 19 2 27 1 25 3 15
Iesire
142