Nông dân John đang đưa các con bò của anh ta đi xem phim! Xe tải của anh ta thì có sức chứa có hạn thôi, là ~C~ ~(100 \le C \le 5000)~ kg, anh ta muốn đưa ~1~ số con bò đi xem phim sao cho tổng khối lượng của đống bò này là lớn nhất, đồng thời xe tải của anh ta vẫn chịu được.

Cho ~N~ ~(1 \le N \le 16)~ con bò và khối lượng ~W_i~ của từng con, hãy cho biết khối lượng bò lớn nhất mà John có thể đưa đi xem phim là bao nhiêu.

Input

• Dòng ~1~: ~2~ số nguyên cách nhau bởi dấu cách: ~C~ và ~N~
• Dòng ~2~ ...~N + 1~: Dòng ~i + 1~ chứa ~1~ số nguyên: ~W_i~

Output

• Dòng ~1~: Một số nguyên là tổng khối lượng bò lớn nhất mà John có thể mang đi xem phim.

Sample Input

259 5
81
58
42
33
61

Sample Output

242

Note

~81 + 58 + 42 + 61 = 242~; đây là tổng khối lượng bò lớn nhất có thể được.