Poçt göndərişi

Russian Code Cup müsabiqəsinin yekun mərhələsinə hazırlıq məqsədi ilə təşkilatçılara müsabiqənin keçiriləcəyi yerə $n$ əşya göndərmək lazım idi. Hər bir əşyanın $m_i$ qramla çəkisi məlumdur.

Göndərmək üçün "Superekspres" poçt xidmətindən istifadə etmək qərarına gəlindi. Xidmət hər birində bir və ya bir neçə əşyanın göndərilə biləcəyi bağlamaları göndərmək üçün qəbul edir. Bu zaman bağlamanın çəkisi onda göndərilən əşyaların ümumi çəkisinə bərabərdir.

Bağlamanın göndərilməsi (xüsusi şərtə bağlı bağlamalardan başqa) hər qramına görə $1$ manatdır. Xüsusilə də bağlama tam bir kiloqramdırsa, onda onun göndərilmə qiyməti $p$ manatdır.

Russian Code Cup müsabiqəsinin təşkilatçıları az sayda məsrəflə bütün əşyaları göndərmək istəyirlər. Buna nail olmaq üçün bağlamalara görə əşyaları paylaşmaqda onlara kömək edin.

Giriş verilənləri

İlk sətir xüsusi şərtə bağlı olaraq bağlamaların sayı və göndərmə qiymətini ifadə edən iki $n$ və $p(1\le n\le 14,1\le p\le 1000)$ ədədlərini ehtiva edir. İkinci sətir $n$ tam ədədi ehtiva edir: $m_1,m_2,...,m_n(1\le m_i\le 1000$ hər bir $i$ üçün $1$-dən $n$-ə qədər).

Çıxış verilənləri

Yeganə ədədi — bütün əşyaları göndərmək üçün minimal ümumi məbləği manatla verin.

Nümunələr