banuti

Banuti

== include(page="template/taskheader" task_id="banuti") ==

Taranul Victor are la dispozitie $N$ tipuri de bancnote, fiecare in numar nelimitat. El este curios  care este suma minima $Smin$, astfel incat orice suma mai mare ca $Smin$ sa poata fi platita din bancnotele pe care le are la dispozitie.

Taranul Victor are la dispozitie $N$ tipuri de bancnote, fiecare in numar nelimitat. El este curios care este suma minima $Smin$, astfel incat orice suma mai mare ca $Smin$ sa poata fi platita din bancnotele pe care le are la dispozitie.

h2. Cerinta

h2. Date de intrare

Pe prima linie a fisierului $banuti.in$ se afla numarul $N$. Pe urmatoarea linie se afla $N$ numere $V$<sub>i</sub> care reprezinta valoarea fiecarui tip de bancnota.

Pe prima linie a fisierului $banuti.in$ se afla numarul $N$. Pe urmatoarea linie se afla $N$ numere $V{~i~}$ care reprezinta valoarea fiecarui tip de bancnota.

h2. Date de iesire

h2. Restrictii

* $2 ≤ N ≤ 50000$
* $1 < $V$<sub>i</sub> &le; 10 000 000$

* $2 ≤ N ≤ 50 000$
* {$1 ≤ V{~i~} ≤ 10 000 000$}

* Se garanteaza ca exista cel putin o bancnota cu valoarea $≤ 5000$.
* $Smin < 1 000 000 000$

* Pentru $20%$ din teste $N ≤ 50$, $Smin ≤ 100 000$ si valoarea minima a cel putin unei bancnote $≤ 200$.
* Pentru $50%$ din teste $N ≤ 1000$.

h2. Exemplu

|
== include(page="template/taskfooter" task_id="banuti") ==

2103