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 |
Tesztadatok
