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


Submit solution

Points: 2
Time limit: 1.0s
Memory limit: 98M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

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à \(19\)có tổng là \(36\)

tichpx

Comments

There are no comments at the moment.