0/1 Knapsack Maximum Weight

Given a set of items with their weights and a knapsack with a limited capacity, determine the maximum total weight that can be carried without exceeding the capacity. This is a typical (0/1) knapsack problem where each item can either be selected or not selected. Formally, if you are given a list of weights (W = [w_1, w_2, \dots, w_n]) and a maximum capacity (M), your goal is to choose a subset of (W) such that the sum of the selected weights is maximized and does not exceed (M).

inputFormat

The input is given via standard input (stdin). The first line contains two integers (n) and (M) where (n) is the number of items and (M) is the maximum capacity of the knapsack. The second line contains (n) space-separated integers representing the weights of the items.

outputFormat

Output a single integer to standard output (stdout) representing the maximum total weight that can be carried without exceeding the capacity.## sample

4 7
1 3 4 5

7