#837. PACKING - Xếp đồ chơi

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

n đồ chơi được đánh số từ 1 đến n . Đồ chơi thứ i có thể tích là v_i . Có một cái hộp thể tích V . Cần xếp các đồ chơi vào hộp sao cho tổng thể tích của các đồ chơi không được vượt quá thể tích của hộp.

Yêu cầu: Hãy tính tổng thể tích lớn nhất của các đồ chơi có thể xếp vào hộp.

Dữ liệu vào:

  • Dòng đầu tiên ghi hai số n V là số đồ chơi và thể tích của hộp (1≤n≤30;1≤V≤10^5 ) ;
  • Dòng thứ hai ghi n số nguyên dương v_1,v_2,…,v_n\ (1≤v_i≤10^4 ) .

Hai số liên tiếp được ghi cách nhau một khoảng trắng.

Dữ liệu ra:

  • Một số nguyên duy nhất là tổng thể tích lớn nhất của các đồ chơi có thể xếp vào hộp.

Ví dụ:

Dữ liệu vào:
5 9
2 3 3 2 4
Dữ liệu ra:
9