Giải bài trực tuyến

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 <= C <= 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 <= N <= 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.

Dữ liệu

• 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

Kết quả

• 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.

Ví dụ

Dữ liệu
259 5
81
58
42
33
61

Kết quả
242

Giải thích

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