Minimum Box Packing Problem

You are given n items with their individual weights and a box that can hold a maximum total weight of W. Your task is to determine the minimum number of boxes required to pack all items such that the sum of the weights in any box does not exceed W. If any individual item has a weight strictly greater than W, then it is impossible to pack that item and you should output −1.

This problem can be viewed as a constrained bin packing problem. Formally, if the weights are \(w_1, w_2, \dots, w_n\), then for each item \(w_i\) we require \(w_i \le W\). The goal is to partition the items into the minimum number of boxes, where the sum of items in each box is \(\le W\). For example, if n = 5, W = 10, and the weights are [2, 5, 4, 7, 1], one optimal solution uses 2 boxes.

inputFormat

The input is given via standard input (stdin) and consists of two lines. The first line contains two integers n and W where n is the number of items and W is the maximum weight a box can hold. The second line contains n integers representing the weights of the items.

Constraints:

• \(1 \le n \le 10^5\)
• \(1 \le W \le 10^9\)
• \(1 \le w_i \le 10^9\)

outputFormat

Output a single integer: the minimum number of boxes required. If any item exceeds the permissible weight W, output -1.

## sample

5 10
2 5 4 7 1

2

</p>