Maximum Value Under Budget

Given a list of items with positive integer values and a budget, determine the maximum total value you can obtain by choosing a subset of items without exceeding the given budget. You cannot pick an item more than once. This problem is a variation of the 0/1 knapsack problem where each item's weight is equal to its value.

Mathematical Formulation: Given a set of values \(\{v_1, v_2, \dots, v_n\}\) and a budget \(B\), find a subset \(S \subseteq \{1,2,\dots,n\}\) such that \(\sum_{i \in S} v_i \le B\) and \(\sum_{i \in S} v_i\) is maximized.

inputFormat

The input is given from standard input in the following format:

1. The first line contains an integer (n) representing the number of items.
2. The second line contains (n) space-separated positive integers representing the values of the items.
3. The third line contains an integer (B), the budget.

outputFormat

Output a single integer to standard output representing the maximum total value of a subset of items such that their sum does not exceed the budget.## sample

5
2 2 4 5 1
10

10