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.
 
h2. Cerinta
 
Cunoscand valorile celor $N$ tipuri de bancnote, aflati $Smin$.

Poveste si cerinta...

h2. Date de intrare

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

Pe prima linie a fisierului $banuti.out$ se gaseste numarul $Smin$ sau $-1$, daca nu exista solutie.

...

h2. Restrictii

* $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 &le; 50$, $Smin &le; 100 000$ si valoarea minima a cel putin unei bancnote $&le; 200$.
* Pentru $50%$ din teste $N &le; 1000$.

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. banuti.in |_. banuti.out |

| 2
3 5
| 7
|
| 2
3 6
| -1
|
 
== include(page="template/taskfooter" task_id="banuti") ==

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
h3. Explicatie
...
== include(page="template/taskfooter" task_id="banuti") ==

2103