Minimum Shelves

You are given a shelf with a maximum weight capacity \(W\) and \(B\) boxes with specified weights. Your task is to determine the minimum number of shelves required to store all the boxes without exceeding the weight limit on any shelf.

For each test case, boxes can be placed on a shelf as long as the cumulative weight does not exceed \(W\). When a box cannot be added to any existing shelf, a new shelf must be started. A greedy strategy is used by first sorting the boxes in descending order to try and pack the heaviest boxes first.

The input consists of multiple test cases, and the process stops when a line with two zeros is encountered. It is guaranteed that the greedy method applied in this problem will yield the correct answer.

inputFormat

The input consists of multiple test cases. Each test case contains two lines:

• The first line contains two integers \(W\) and \(B\), where \(W\) is the maximum weight capacity of a shelf and \(B\) is the number of boxes.
• The second line contains \(B\) space-separated integers representing the weights of the boxes. If \(B = 0\), this line may be empty.

The input terminates with a line containing two zeros: 0 0.

outputFormat

For each test case, output a single line with one integer indicating the minimum number of shelves required to store all boxes.

## sample

100 5
50 30 70 10 20
0 0

2

</p>