Maria exagerează cu convorbirile pe telefonul mobil. Prin urmare, părinţii au decis să îi anuleze abonamentul.
Totuşi, i-au permis să cumpere cartele telefonice care în total să îi permită să vorbească cel puţin M minute.
Există 31 de tipuri de cartele telefonice, numerotate de la 0 la 30. Cartela i (0<=i<=30) costă 2ⁱ lei şi permite a_i minute de convorbiri.

Cerinţă

Să se determine suma minimă de bani pe care trebuie să o cheltuiască Maria pentru a cumpăra cartele telefonice pentru cel puţin M minute de convorbiri.

Date de intrare

Fişierul de intrare mobil.in conţine pe prima linie numărul natural M. Pe cea de a doua linie se află numerele naturale a₀ a₁ ... a₃₀ separate prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire mobil.out va conţine o singură linie pe care va fi scris un număr natural reprezentând suma minimă cheltuită pentru achiziţionarea cartelelor ce permit cel puţin M minute de convorbiri.

Restricţii

• 1 ≤ M ≤ 10⁹
• 1 ≤ a_i ≤ 10⁹, 0 ≤ i ≤ 30
• Pentru teste valorând în total 60 puncte M ≤100 000.
• Pot fi cumpărate mai multe cartele de acelaşi tip.

Exemple

mobil.in	mobil.out	Explicatie
11 1 1 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1	5	Trebuie sa cumpar cartele care sa imi asigure cel putin 11 minute de convorbiri. Aleg cartela 2 (care costa 4 lei si imi asigura 10 minute de convorbiri) si cartela 0 (care costa 1 leu si imi asigura 1 minut de convorbiri).

prof. Emanuela Cerchez

Liceul de Informatică „Grigore Moisil” Iaşi

emanuela.cerchez@gmail.com