Maximum Difficulty Sum

You are given n challenges, each with a difficulty rating, and an integer D representing the maximum allowed total difficulty. Your task is to select a subset of challenges such that the sum of their difficulty ratings is as large as possible but does not exceed D.

Formally, given a list of difficulties \(d_1, d_2, \dots, d_n\), choose a subset \(S\) such that:

\(\sum_{i \in S} d_i \le D\)

and maximize \(\sum_{i \in S} d_i\). If no subset satisfies the constraint, output 0.

Note: Each challenge can be selected at most once.

inputFormat

The first line contains two integers n and D (0 ≤ n ≤ 10⁵, 0 ≤ D ≤ 10⁹), where n is the number of challenges and D is the maximum allowed difficulty sum.

The second line contains n space-separated integers, representing the difficulty ratings of the challenges. If n is 0, the second line will be empty.

outputFormat

Output a single integer, the maximum possible sum of difficulty ratings of a chosen subset that does not exceed D.

5 10
1 2 3 4 5

10