E2 - Mince

Časový limit: 10s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3.4, Python 3.11

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Matúš sa po sledovaní všetkých správ ako je všetko v blízkom zahraničí lacnejšie rozhodol vybrať na nákupy do Poľska. Zamenil si naše eurá za poľský zlotý. Keďže tam ale často nechodí, chcel by minúť čo najviac mincí (zlotych). Zvyšné mince by mu boli len na obtiaž, vymienať sa ich nedá, resp. neoplatí. Pomôžte mu, ktorými mincami má platiť pri poslednom nákupe tak, aby mu ich zostalo v peňaženke čo najmenej.

Úloha

Napíšte program, ktorý vypíše maximálny počet platidiel, ktorými sa dá zaplatiť zadaná suma.

Vstup

Prvý riadok obsahuje kladné celé číslo N - počet mincí.
Druhý riadok obsahuje N nezáporných celých čísel 1 ≤ h_i ≤ 5.000 - hodnoty mincí.
Tretí riadok obsahuje kladné celé číslo 1 ≤ S &le 1.000.000 - sumu, ktorú má Matúš zaplatiť.

E1

1 ≤ N ≤ 20

E2

1 ≤ N ≤ 1.000

Výstup

Výstup obsahuje jedno kladné celé číslo, maximálny počet mincí. V prípade, že danú sumu nie je možné zaplatiť, výstupom bude riadok obsahujúci číslo 0.

Príklad

Vstup

5
1 3 3 5 2
11

Výstup

07 Finále 2