Pályázatok
Olimpiai válogatóverseny 2001
Mohó Márton vállalkozó egy pályázaton meghirdetett munkák között válogat. Ismeri minden munka határidejét, és azt, hogy az adott munka elvégzése mekkora hasznot eredményez. Minden munka elvégzésére 1 napra van szüksége, és egy nap csak egy munkát tud elvégezni.
Feladat
Készíts programot, amely kiszámítja, hogy
- mekkora az elérhető legnagyobb összhaszon,
- mely munkákat végezzük el, hogy az összhaszon a lehető legnagyobb legyen!
Bemenet
A bemenet szöveges állomány első sora a munkák N (0<N<=10000) számát tartalmazza. A további N sor mindegyike két egész számot tartalmaz egy szóközzel elválasztva. Az első szám, H a munka határideje (0<H<10000), a második P pedig a munka elvégzésével elérhető haszon (0<P<1000). Ha egy munka hatrárideje K, az azt jelenti, hogy ha a munkát elvállaljuk, akkor azt a K-adik napig (a K. napon még lehet) be kell fejezni.
Kimenet
A kimenet szöveges állomány első sorába az elérhető legnagyobb összhaszont kell írni! A második sorba azoknak a munkáknak a sorszámait kell kiírni, amelyek elvégzése az első sorba írt összhasznot eredményezi, ha a munkákat ebben a sorrendben végzik el, azaz a sorban az i-edik munkát az i-edik napon.
Példa
| UTEMEZ.BE |
UTEMEZ.KI |
6
3 60
4 40
1 10
3 30
7 70
4 20
|
220
6 4 1 2 5
|
Tesztadatok
