Cho \(n\) vật, vật \(i\) có trọng lượng \(w_i\). Hãy chọn một tập con có tổng trọng lượng bé hơn hoặc bằng \(M\) và tổng đó là lớn nhất.
\InputFile
Dòng đầu chứa hai số nguyên \(n, M\).
Dòng tiếp theo chứa \(n\) số nguyên \(w_1, w_2, \ldots, w_n\).
Giới hạn: \(1 \le n \le 50\), \(1 \le M \le 10^9\), \(1 \le w_i \le 10^9\).
\OutputFile
In ra một số nguyên là tổng lớn nhất thỏa mãn đề bài.
Lưu ý: một tập con là một tập bất kì các phần tử, không nhất thiết phải liên tiếp.
Example
Test 1
Input
5 10
3 8 2 1 5Output
10
Bình luận
Đăng nhập để bình luận
Chưa có bình luận nào.