Cows in a Skyscraper

Time limit1sMemory limit128 MB

Summary

Given up to 18 cow weights and an elevator capacity, find the minimum number of trips that carry every cow without exceeding the capacity.

Level: Medium6 of 10
Topics: Dynamic programming, Bit manipulation, Greedy, Brute force
Solved: No attempts yet

Problem

A little-known fact about Bessie and her friends is that they love stair-climbing races. A better-known fact is that cows really dislike going down stairs. So after the cows finish racing to the top of their favorite skyscraper, they run into a problem: refusing to walk back down the stairs, they must use the elevator to return to the ground floor.

The elevator has a maximum weight capacity of $W$ pounds, and cow $i$ weighs $C_i$ pounds. Help Bessie bring all $N$ cows down to the ground floor using the fewest possible elevator rides. On each ride, the total weight of the cows aboard must not exceed $W$ .

Report only the minimum number of rides.

Constraints: $1 \le N \le 18$ , $1 \le W \le 10^8$ , $1 \le C_i \le W$ .

Input

Line 1: two integers $N$ and $W$ , separated by a space.
Lines 2 to $N+1$ : line $i+1$ contains the integer $C_i$ , the weight of one cow.

Output

Print a single integer: the minimum number of elevator rides needed to bring all the cows to the ground floor.

Hint

In the sample there are four cows weighing 5, 6, 3, and 7 pounds, and the elevator can carry at most 10 pounds. The cow weighing 3 can share a ride with any one other cow, but each of the other three cows is too heavy to be paired with another. Therefore at least 3 rides are required.

Examples1

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