Bin Packing

Time limit4sMemory limit256 MB

Summary

Given up to 24 item weights and a bin capacity S, find the minimum number of bins that hold all items with each bin's total weight at most S.

Level: Medium7 of 10
Topics: Dynamic programming, Bit manipulation, Backtracking, Greedy
Solved: No attempts yet

Problem

You are given $n$ objects of weights $w\_1, w\_2, \ldots, w\_n$ . Pack all $n$ objects into the minimum number of bins such that the total weight of the objects in any bin is at most $S$ .

Input

The first line contains two integers $n$ and $S$ , where $1 \leq n \leq 24$ and $1 \leq S \leq 10^8$ . The second line contains $w\_1, w\_2, \ldots, w\_n$ , where $1 \leq w\_i \leq S$ .

Output

Print the minimum number of bins required to pack the given objects.

Hint

The objects can be packed into three bins of size 10 as follows: [5,3], [6], [7]. It is impossible to pack them into two bins because their total weight is 21.

Examples1

Example 1
Input
```
4 10
5 6 3 7
```
Expected output
```
3
```