Çubuğun kəsilməsi

Siz taxta çubuğu hissələrə bölməlisiniz. Ən əlçatan şirkət olan The Analog Cutting Machinery, Inc. (ACM) kəsilən çubuğun uzunluğuna görə ödəniş alır. Onların iş qaydası yalnız bir dəfə kəsməyə icazə verir.

Asanlıqla görmək olar ki, kəsimlərin fərqli ardıcıllığı fərqli qiymətlərə səbəb olur. Məsələn, bir ucundan $2,4$ və $7$ metr nöqtələrində kəsilməli olan $10$ metr uzunluğunda çubuğu nəzərdən keçirək. Bir neçə variantı nəzərdən keçirək.

• Əvvəlcə $2$-də, sonra $4$-də, daha sonra $7$-də kəsə bilərsiniz. Bu, $10+8+6=24$ qiymətinə səbəb olacaq, çünki birinci çubuq $10$ metr, ikinci $8$ metr, üçüncü isə $6$ metr idi.

• Digər variantda əvvəlcə $4$-də, sonra $2$-də, daha sonra $7$-də kəsəcəyik. Bu, $10+4+6=20$ qiymətinə səbəb olacaq ki, bu da ən yaxşı qiymətdir.

Rəhbəriniz sizin kompüter bacarıqlarınıza etibar edir ki, verilmiş çubuğun kəsilməsinin minimal qiymətini müəyyən edəsiniz.

Giriş verilənləri

Bir neçə testdən ibarətdir. Hər testin ilk sətiri kəsilməli olan çubuğun uzunluğunu $l(l<1000)$ ehtiva edir. Növbəti sətir ediləcək kəsimlərin sayını $n(n<50)$ ehtiva edir.

Növbəti sətir $n$ müsbət ədədi $c_i(0<c_i<l)$ ehtiva edir ki, bunlar kəsim nöqtələrini təmsil edir və ciddi artan sırada verilir. $l=0$ olan sətir giriş məlumatlarının sonunu göstərir.

Çıxış verilənləri

Çubuğun kəsilməsinin minimal qiymətini nümunədə göstərilən formatda çıxarın.

Nümunələr