Đi xem phim

View as PDF

Submit solution


Points: 0.05 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
USACO US-Open 2008 - Bảng Đồng
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.