Olimpiya baqajı

Londonda olarkən Vasya özü, ailəsi və dostları üçün çoxlu müxtəlif suvenir və hədiyyələr aldı. Lakin, hava limanında evə bilet alarkən, böyük təəccüblə öyrəndi ki, onun baqajının ümumi çəkisi m qramdan çox olmamalıdır.

Vasyanın aldığı suvenir və hədiyyələrin sayını bilə-bilə, ona baqajını elə yığmağa kömək edin ki, o, mümkün qədər sərhədə yaxın olsun və, əlbəttə ki, aviareysin məhdudiyyətlərini aşmasın.

Giriş məlumatları

Birinci sətirdə aviareys üçün baqaj məhdudiyyəti m (1 ≤ m ≤ 10000) və Vasyanın əşyalarının sayı n (1 ≤ n ≤ 300) verilir.

İkinci sətirdə Vasyanın hər bir əşyasının müvafiq çəkisi olan n ədəd var. Məlumdur ki, hər bir əşyanın çəkisi 100000 qramı keçmir.

Çıxış məlumatları

Tək bir ədəd çıxarın - Vasyanın baqajının maksimal icazə verilən çəkisi.

Nümunələr