시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 256 MB97321651.613%

문제

You're given a collection of $n$ objects of weights $w_1, w_2, \ldots, w_n$. You have to pack all $n$ objects into the minimum number of bins under the constraint that the total weight of all the objects in any bin is bounded by $S$.

입력

The first line contains a pair of 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$.

출력

The output is just the minimum number of bins required to pack the given objects.

예제 입력 1

4 10
5 6 3 7

예제 출력 1

3

힌트

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 size is 21.