Tagy: bruteforce
Obtiažnosť: easy

Zlodej

Zo svojej ultraľahkej kuše ste vystrelili šíp s hákom, za ktorým sa tiahlo tenké, no pevné lano. Hák sa zachytil na rebríku neďalekej budovy. Potichu ako mačka prerúčkujete cez lano, ktoré je teraz vo výške dvadsiatich metrov. Nepozeráte sa dole, svoj cieľ máte pred sebou.

Zoskočíte na balkón prominentného milionára. Vytiahnete vašu najnovšiu hračku, laserový rezač skla, pomocou ktorého spravíte dieru do sklenej výplne. Opatrne si otvoríte dvere a potichu sa vtiahnete dnu. Do vzduchu pred sebou nastriekate aerosolový sprej. Hneď sa pred vami objaví slabo svietiaca červená sieť poplašného zariadenia.

V štýle profesionálneho gymnastu sa prehýbate medzi červenými lúčmi až nakoniec skončíte uprostred obývačky. V obývačke je nn rôznych vecí. Je vám jedno, ktoré z nich zoberiete, lebo všetky majú obrovskú cenu. Každá má však nejakú hmotnosť a batoh, ktorý máte na chrbte unesie len ww váhy. A vy chcete svoj batoh naplniť čo najviac. Aká je najväčšia hmotnosť nepresahujúca ww, ktorú viete zbaliť?

Úloha

Na vstupe dostanete číslo nn a ww -- počet predmetov a váhu, ktorú unesie batoh. Pre každú z vecí dostanete hodnotu viv_i -- hmotnosť ii-teho objektu. Zistite, akú najväčšiu hmotnosť viete nabaliť do batoha s nosnosťou ww použitím daných predmetov.

Vstup

Prvý riadok obsahuje dve čísla nn a ww (1n251 \leq n \leq 25, 1w1091\leq w \leq 10^9) -- počet vecí a nosnosť batoha.

Druhý riadok obsahuje nn celých čísel v1v_1vnv_n (1vi100001 \leq v_i \leq 10\,000 ) -- váhy jednotlivých vecí.

Výstup

Jedno celé číslo -- maximálnu hmotnosť vecí, ktoré si vieš zbaliť do batoha vzhľadom na jeho obmedzenú hmotnosť.

Príklady

Vstup

Výstup

3 5
5 2 2
5

Použitím dvoch vecí s váhou 22 dosiahnem len objem 44. Iné možnosti presiahnu nosnosť batoha.

Ak chceš riešiť túto úlohu, musíš sa najprv prihlásiť.