题目描述

From USACO12MAR

A little known fact about Bessie and friends is that they love stair climbing races. A better known fact is that cows really don't like going down stairs. So after the cows finish racing to the top of their favorite skyscraper, they had a problem. Refusing to climb back down using the stairs, the cows are forced to use the elevator in order to get back to the ground floor.

人人皆知，贝西和朋友们喜欢爬楼梯比赛，一个更广为人知的事实是，奶牛们不喜欢下楼梯。因此，当奶牛跑到他们最喜欢的摩天大楼的顶部时，奶牛们拒绝走楼梯下去，而不得已乘坐电梯回到一楼。

The elevator has a maximum weight capacity of W (1 <= W <= 100,000,000) pounds and cow i weighs C_i (1 <= C_i <= W) pounds. Please help Bessie figure out how to get all the N (1 <= N <= 18) of the cows to the ground floor using the least number of elevator rides. The sum of the weights of the cows on each elevator ride must be no larger than W.

这个电梯有一个最大载重W (1 <= W <= 100,000,000)。现在告诉你每头奶牛的重量Ci，请你帮助Bessie给这N（N<=18）头奶牛分组，分在同一组的奶牛将乘坐同一趟电梯，但不能超过电梯的最大载重M，请问最少分组数为多少？

输入格式

第 1行有2 个整数N，W，分别表示奶牛数量和电梯最大载重；

接下来的 n 个正整数，表示N头奶牛的重量Ci。

输出格式

输出一个整数，代表最小划分的组数。

样例 #1

样例输入 #1

4 10 
5 
6 
3 
7

样例输出 #1

3

数据范围

N<=18，W在INT范围内