Minimum Removals on Conveyor Belt

You are given a conveyor belt with n boxes, where each box has a weight. The conveyor belt has a weight capacity C. Your task is to remove the minimum number of boxes so that the total weight of the remaining boxes does not exceed C. If the total weight is already within the capacity, no boxes need to be removed. If even after removing boxes the remaining total weight cannot be made less than or equal to C, output -1.

Problem Explanation:

• Let the weights be \(w_1, w_2, \dots, w_n\) and capacity be \(C\).
• You need to choose a subset of boxes to remove such that the sum of the weights of the remaining boxes \(\sum_{i \in R} w_i \le C\).
• To minimize the number of removals, consider removing the heaviest boxes first.

Example:
For example, if the weights are [10, 20, 30, 40, 50] and C = 100, removing the box with weight 50 reduces the total weight from 150 to 100, so the answer is 1.

inputFormat

The input is read from standard input (stdin) and has the following format:

n C
w1 w2 ... wn

where n is the number of boxes, C is the capacity of the conveyor belt, and w1, w2, ..., wn are the weights of the boxes.

outputFormat

Output a single integer to standard output (stdout), which is the minimum number of removals required so that the sum of the weights of the remaining boxes does not exceed C. If it is not possible to reach the desired capacity, output -1.

5 100
10 20 30 40 50

1