Maximize Happiness

Anna has a collection of n unique toys, each providing a certain happiness value. She wishes to select a subset of these toys such that the total sum of their happiness values is maximized, but without exceeding a given threshold T. This is a variant of the classic 0/1 knapsack problem where the weight of each item is its happiness value and each item can be used at most once.

Your task is to compute the maximum possible sum of happiness values that does not exceed the threshold T.

The problem can be mathematically formulated as follows:

Given a set of numbers \(a_1, a_2, \ldots, a_n\) and a threshold \(T\), find a subset \(S\) such that \[ \sum_{i \in S} a_i \le T \quad \text{and} \quad \sum_{i \in S} a_i \text{ is maximized.} \]

inputFormat

The first line of input contains two integers n and T, where n denotes the number of toys and T is the maximum allowed total happiness value.

The second line contains n space-separated integers representing the happiness values of the toys.

outputFormat

Output a single integer which is the maximum sum of happiness values obtainable without exceeding T.

5 50
10 20 30 40 50

50