#367. CHUNGCAKE - Bánh Chưng

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: Trùm CUỐI

Đề bài

Nhân dịp Tết nguyên đán năm nay, Nhà trường tổ chức cho các lớp gói bánh Chưng. Có nhiều lớp tham gia, các lớp đã gói được n cái bánh Chưng, cái thứ i có thể tích là số nguyên dương v_i (cm^3) . Tuy nhiên để luộc những cái bánh này thì lại chỉ có duy nhất một cái nồi với thể tích là V (cm^3) và số củi chỉ đủ để luộc duy nhất một nồi. Bạn hãy tính xem có thể luộc được số bánh Chưng với tổng thể tích lớn nhất là bao nhiêu (số bánh Chưng luộc được phải có tổng thể tích không vượt quá thể tích của nồi)?

Dữ liệu:

  • Dòng đầu chứa hai số nguyên dương n V ;
  • Dòng thứ hai chứa n số nguyên dương v_i .

Hai số liên tiếp trên một dòng được ghi cách nhau một dấu cách.

Kết quả:

  • Một số nguyên duy nhất là tổng thể tích lớn nhất của số bánh Chưng luộc được.

Ví dụ:

Dữ liệu:

3 8
2 3 4

Kết quả:

7

Dữ liệu:

4 10
1 2 3 4

Kết quả:

10

Giới hạn:

  • 1 ≤ n ≤ 30; 1 ≤ V ≤ 2000; 1 ≤ v_i ≤ 100