翰翰和达达饲养了  只小猫,这天,小猫们要去爬山。

经历了千辛万苦,小猫们终于爬上了山顶,但是疲倦的它们再也不想徒步走下山了(呜咕>_<)。

翰翰和达达只好花钱让它们坐索道下山。

索道上的缆车最大承重量为 ,而  只小猫的重量分别是 

当然,每辆缆车上的小猫的重量之和不能超过 

每租用一辆缆车,翰翰和达达就要付  美元,所以他们想知道,最少需要付多少美元才能把这  只小猫都运送下山?

输入格式

第  行:包含两个用空格隔开的整数, 和 

第  行:每行一个整数,其中第  行的整数表示第  只小猫的重量 

输出格式

输出一个整数,表示最少需要多少美元,也就是最少需要多少辆缆车。

数据范围


输入样例:

5 1996
1
2
1994
12
29

输出样例:

2

思路

搜索顺序类似于分成互质组, 枚举组数。

这里剪枝是终点: 首先看能不能优化搜索顺序, 先放轻的猫还是先放重的猫。显然是重的猫分支少。 故这里把猫排序, 从重的开始枚举。

代码

const int N = 20;
int n, w;
int a[N];
int sum[N];
int ans = 20;
void dfs(int u, int k)
{
    if (k >= ans)
        return;
    if (u == n)
    {
        ans = k;
        return;
    }
    for (int i = 0; i < k; i++)
    {
        if (sum[i] + a[u] <= w)
        {
            sum[i] += a[u];
            dfs(u + 1, k);
            sum[i] -= a[u];
        }
    }
    sum[k] = a[u];
    dfs(u + 1, k + 1);
    sum[k] = 0;
}
 
int main()
{
    cin >> n >> w;
    for (int i = 0; i < n; i++)
        cin >> a[i];
 
    sort(a, a + n, greater<int>());
    dfs(0, 0);
 
    cout << ans << endl;
    return 0;
}