Bài toán cái túi

Xem dạng PDF

Gửi bài giải

Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, PyPy, Python

Cho n đồ vật kích thước là ~a_1,a_2,...,a_n~ và một cái túi có kích thước là ~M~

Nhiệm vụ của bạn là hãy lựa chọn các đồ vật xếp vào túi cho hợp lý sao cho tổng kích thước được chọn không vượt quá kích thước túi mà nhưng phải lớn nhất có thể

Input

Dòng đầu gồm hai số nguyên dương là số đồ vật ~n (1 \le n \le 20)~ và kích thước túi ~M ((1 \le M \le 1000))~

Dòng cuối là ~n~ số nguyên dương tương ứng với kích thước các đồ vật có giá trị không vượt quá ~1000~

Ouput

Một số tự nhiên là kích thước thu được lớn nhất có thể của cái túi, tất nhiên nếu không xếp được đồ vật nào thì xuất ra ~0~

Ví dụ

Input

4 40
17 26 19 8

Ouput

36

Giải thích Ta chọn 2 đồ vật kích thước là 17 và 19có tổng là 36


Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.