60. Maximum Subset Sum Not Exceeding K

Difficulty: medium · Dynamic Programming, Bit Manipulation

Problem

Given an array of positive integers and an integer `K`, choose any subset of the elements (possibly empty) so that its sum does not exceed `K`. Print the largest such sum.

Input

- Line 1: the array elements, separated by spaces. - Line 2: the integer `K`.

Output

Print the maximum subset sum that is at most `K`.

Example 1

Input:
2 3 5 7
10
Output:
10

Explanation: 2 + 3 + 5 = 10 (or 3 + 7) reaches K exactly.

Example 2

Input:
6 9 14
12
Output:
9

Explanation: Possible sums at most 12 are 0, 6 and 9; the largest is 9.

Example 3

Input:
50 60
10
Output:
0

Explanation: Every element is larger than K, so only the empty subset fits: 0.

Constraints

- 1 <= number of elements <= 100 - 1 <= each element <= 10^5 - 1 <= K <= 10^5

Solutions are judged against 3 sample and 8 hidden tests. Sign in to solve it · All problems