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 |