Linh có \(n\) món đồ, và muốn cho hết chúng vào các thùng.
Món đồ thứ \(i\) nặng \(w_i\).
Biết rằng mỗi thùng chỉ chịu được tổng cân nặng không vượt quá \(W\).
Hỏi số lượng thùng ít nhất Linh phải dùng là bao nhiêu?
\InputFile
Dòng đầu tiên gồm hai số nguyên \(n\) và \(W\).
Dòng thứ hai gồm \(n\) số nguyên \(w_i\).
\OutputFile
In ra số thùng ít nhất Linh cần dùng.
Điều kiện
- \(1 \le n \le 20\).
- \(1 \le w_i \le W \le 10^9\).
Example
Test 1
Input
4 5
1 2 3 4Output
2
Bình luận
Đăng nhập để bình luận
Chưa có bình luận nào.