#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 vào:

  • 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.

Dữ liệu ra:

  • 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 vào:
3 8
2 3 4
Dữ liệu ra:
7
Dữ liệu vào:
4 10
1 2 3 4
Dữ liệu ra:
10

Giới hạn:

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