Closest Sum to Target

You are given a target weight and a list of object weights. Your task is to find the maximum possible sum of some weights that does not exceed the given target.

Formally, given an integer \(T\) (the target) and a list of \(n\) integers \(w_1, w_2, \dots, w_n\), find a subset of these weights such that the sum of the subset is as large as possible but does not exceed \(T\). If no weights can be chosen without exceeding \(T\), output 0.

This problem is a typical variation of the subset sum problem and can be solved using dynamic programming techniques.

inputFormat

The input is given via standard input (stdin) and consists of two lines:

• The first line contains two integers \(n\) and \(T\), where \(n\) is the number of weights and \(T\) is the target weight.
• If \(n > 0\), the second line contains \(n\) space-separated integers representing the weights. If \(n = 0\), the second line may be empty.

outputFormat

Output a single integer via standard output (stdout) which is the maximum sum not exceeding the target \(T\).

5 50
10 20 30 40 50

50