excursie

Pentru a castiga cat mai multi clienti, o companie de cai ferate a adoptat o strategie speciala: pe traseele sale se vand m tipuri de bilete (numerotate de la 1 la m). Un calator care cumpara un bilet de tipul i poate circula

Distanta (km) 10 20 30 40 50 60 70 80 90 100
Pret (lei) 12 21 31 40 49 58 69 79 90 101

i*10 km fara oprire si plateste un pret fix pi. De exemplu, pentru m=10:
Un turist isi planifica sa parcurga cu trenul exact n kilometri (n - multiplu de 10).

Cerinta
Scrieti un program care sa determine suma minima pe care trebuie sa o cheltuiasca turistul pentru a parcurge exact n km.

Date de intrare

Fisierul de intrare excursie.in contine pe prima linie valorile n si m separate printr-un spatiu. Pe urmatoarele m linii se afla cate un intreg reprezentand cele m preturi fixe pentru cele m tipuri de bilete.

Date de iesire

Fisierul de iesire excursie.out contine o singura linie pe care se afla un numar natural reprezentand suma minima cheltuita de turist.

Restrictii Exemple

excursie.in

excursie.out

 Explicatii

150 10
12
21
31
40
49
58
69
79
90
101

147

Trebuie parcursi 150 km si compania pune la dispozitie 10 tipuri de bilete. Suma minima cheltuita este de 147 lei si se obtine daca se cumpara un bilet de 31 lei (cu care parcurge exact 30 km) si 2 bilete de 58 lei(cu care parcurge exact 2*60=120 km).

Timp maxim de executie/test: 0.1 secunde.