Çanta

Vasya dostları-proqramçılarla yürüşə çıxmağa hazırlaşır və özü ilə nə götürəcəyini diqqətlə seçmək istəyir. Vasyanın çantasında götürə biləcəyi $n$ əşyası var. Hər əşya 1 kiloqram ağırlığındadır və hər birinin Vasyaya fərqli "faydalılıq" dərəcəsi var.

Yürüşün uzun olacağı gözlənilir və Vasya çantasının çəkisinin $w$ kiloqramdan çox olmasını istəmir.

Vasyaya çantasının çəkisi $w$ kiloqramı keçmədən, əşyaların maksimal ümumi "faydalılığını" tapmaqda kömək edin.

Giriş verilənləri

Birinci sətirdə tam ədədlər $w$ və $n(1\le w,n\le 20)$ verilir. İkinci sətirdə $n$ tam ədəd $c_i(1\le c_i\le 1000)$ — hər bir əşyanın "faydalılığı" göstərilmişdir.

Çıxış verilənləri

Vasyanın özü ilə götürə biləcəyi əşyaların maksimal ümumi "faydalılığını" çıxarın.

Nümunələr