SPOJ in Armenian

Գների աննախադեպ իջեցումից հետո հանրահայտ սուպերմարկետում վաճառվում են 1, 2, 4, …, 2³⁰ դրամ արժողությամբ ապրանքներ, որոնց քաշերը համապատասխանաբար a₀, a₁, ,,,, a₃₀ կիլոգրամ են։ Սակայն գնորդների առջև դրված է մի պայման. Յուրաքանչյուրի կատարած գնումների ընհանուր քաշը պիտի լինի առնվազն M կգ։ Գնորդը կարող է գնել ինչպես տարբեր ապրանքներ, այդպես էլ նույն ապրանքից մի քանի հատ։

Օգնեցեք գնորդին կազմել ամենաէժան զամբյուղը, այսինքն հաշվել այն ամենափոքր գումարը, որը ծախսելով կարող է լցնել զամբյուղն առնվազն M կգ քաշով գնումներով։

Մուտքը

Առաջին տողում գրված է M (1 <= M <= 10⁹) բնական թիվը։ Երկրորդ տողում գրված են 10⁹-ը չգերազանցող a₀, a₁, ,,,, a₃₀ բնական թվերը։

Ելքը

Պետք է արտածել մեկ ամբողջ թիվ՝ այն ամենափոքր գումարը, որ պետք է ծախսել գնումներն իրականացնելու համար։

Օրինակ

Մուտքը.
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