Maximum Difficulty Sum

You are given a set of problems with associated difficulty levels. Your task is to choose a subset of these problems such that the sum of their difficulties is as large as possible but does not exceed a given limit D. This problem is a variation of the 0/1 Knapsack problem. In particular, if we denote the current state by dp[j], the state transition can be written in LaTeX as:

$$dp[j] = \max\{dp[j],\; dp[j-d] + d\}$$

for each difficulty d in the list (provided j - d \ge 0).

Implement a solution that reads the input from stdin and writes the result to stdout.

inputFormat

The first line contains two integers n and D where n is the number of problems and D is the maximum allowed sum of difficulties. The second line contains n space-separated integers representing the difficulty levels of each problem.

outputFormat

Output a single integer representing the maximum sum of difficulties that does not exceed D.

5 10
1 2 3 4 5

10