Minimum Packages Problem

You are given a weight limit \(W\) for a single package and \(n\) items with given weights. Your task is to determine the minimum number of packages required to ship all items such that the total weight in each package does not exceed \(W\).

In each package, you may combine multiple items as long as their total weight does not exceed the limit. You are required to use a greedy approach: first sort the list of item weights in descending order, then repeatedly pick the heaviest item available and try to fill the package with the lightest items (from the end of the sorted list) that fit without exceeding the limit.

Note: It is guaranteed that each individual item weight does not exceed \(W\); however, if an item does exceed the limit, consider it as a separate package.

inputFormat

The input is read from stdin and consists of:

• The first integer \(W\) indicating the weight limit of a single package.
• The second integer \(n\) representing the number of items.
• \(n\) space-separated integers representing the weights of the items.

outputFormat

Output to stdout a single integer which is the minimum number of packages needed to ship all the items.

10 6
7 2 3 9 1 5

3