Teher-fuvar
A feladat szövege
Szállítmányozási vállalkozó vagy és meg kell szervezned teherautód optimális kihasználását. Teherautóddal egy irányban haladsz az úton, mely mentén települések sorakoznak. Minden településen egy adott tömegű csomag várakozik rád, melynek elszállításáért a tulajdonosa adott összeget hajlandó fizetni. Minden csomagot az út legvégén található kikötőig kell elszállítanod, és sosem fordulhatsz vissza, tehát a megadott sorrendben látogatod végig a településeket.
Feladat:
Írj programot ami meghatározza a legnagyobb elérhető összhasznot a megadott bemenethez.
Bemenet:
Az első sor taralmazza a települések 1<=N<=50 számát és a teherautód 1<=K<=200 teherbírását. Az utána következő N sor pedig E és S számokat, ahol 1<=E<=100 a felajánlott fizetség, 1<=S<=200 pedig az áru súlya.
Kimenet:
Az első sora legyen az elérhető legnagyobb haszon, utána pedig következzenek azon települések sorszámai, ahol árut veszünk fel.
Példa
| Input | Output |
| 10 200 23 43 32 12 21 43 32 43 21 43 21 65 21 54 54 65 12 23 34 56 | 164 2 4 8 9 10 |