Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: lmio_1997_3e2_milijonas_vyr.in

Rezultatų failas: lmio_1997_3e2_milijonas_vyr.out

Jei norite pateikti savo sprendimą - prisijunkite.

Kaip panešti milijoną?

Brolių Grimų pasakoje „Šešiese skersai žemės“ šeši draugai nugali suktą karalių.

Norėdamas atsikratyti nemalonių svečių, karalius pasišaukia vieną iš jų ir sako:

– Klausyk, aš tau duosiu tiek aukso, kiek gali panešti ant savo pečių, tik iškeliaukit iš mano karalystės.

Kraudamasis į maišą brangenybes, vaikinas norėtų, kad maiše esančių daiktų svoris būtų kuo mažesnis, o jų vertė – kuo didesnė.

Užduotis

Parašykite programą, kuri patartų, kurias brangenybes verta imti, kurių – ne.

Pradiniai duomenys

Pirmojoje eilutėje pateiktas brangenybių skaičius n bei maksimalus brangenybių, kurias gali panešti vaikinas, svoris s.

Likusiose n eilučių įrašyta kiekvienos brangenybės svoris ir vertė. Brangenybės numeruojamos nuo 1 iki n, t.y. antroje bylos eilutėje įrašyti duomenys apie pirmąją brangenybę, trečioje – apie antrąją ir t. t.

Rezultatai

Į pirmąją eilutę įrašykite brangenybių, kurias siūlytumėte imti, verčių sumą, į antrąją – jų numerius didėjimo tvarka.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
5 10
6 100
4 80
12 500
1 37
5 65
 
182
2 4 5

Ribojimai

1\\leqn\\leq200

s\\leq100