CBOJ Winter Contest Problem 2 - Suitcase Packing

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem type

Bob is dreaming about going on vacation, but before he embarks on his journey, he must pack his bags!

Bob's airport enforces a weight limit of \(W\) kilograms for each suitcase. Bob can pack as many suitcases as he wants, as long as none of them hold items that exceed \(W\) kilograms when added up. As Bob's items are rather bulky, he can only pack a maximum of 2 things into 1 suitcase.

Given a list of \(N\) items Bob wishes to bring, find the minimum number of suitcases Bob needs to carry all his things, with each suitcase being within weight limit!

Note that Python users should submit their solution in PyPy over CPython.

Input Specification

The first line contains two integer \(N\) and \(W\) \((1 \le N \le 10^4, 1 \le W \le 10^9)\), representing the number of items Bob wants to bring and the airport's suitcase weight limit.

The next line contains \(N\) integers with values ranging from \(1\) to \(W\) inclusive, with the \(i\)-th element describing the \(i\)-th item's weight in kilograms.

Note that the weight limit will always be greater than or equal to the heaviest item Bob is planning to pack.

Output Specification

Output an integer, indicating the minimum number of suitcases Bob needs.

Sample Input

4 5
3 2 1 3

Sample Output


Sample Explanation

Bob can pair the items \((1, 3)\) and \((2, 3)\) together, forming suitcases with weights of 4kg and 5kg respectively.


There are no comments at the moment.