165. 小猫爬山
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 20;

int n,k;
int cat[N];
int car[N]; //最多一只小猫一辆车
int ans=99999999;


void dfs(int catID,int carNum)
{
    if(catID==n)
    {
        ans=min(ans,carNum);
        return;
    }
    //剪枝，如果超过了，就不再判断
    //能节省很多时间，否则TLE
    if(carNum>=ans)
    {
        return;
    }
    // 尝试放入车中
    for(int i=1;i<=carNum;i++)  //车的编号从1开始
    {
        if(car[i]+cat[catID]<=k)
        {
            car[i]+=cat[catID];
            dfs(catID+1,carNum);
            car[i]-=cat[catID]; //回溯
        }
    }

    //如果新建车
    carNum++;
    car[carNum]+=cat[catID];
    dfs(catID+1,carNum);
    car[carNum]-=cat[catID];

}

int main()
{
    cin>>n>>k;
    for(int i=0;i<n;i++) scanf("%d",&cat[i]);
    dfs(0,1);
    cout<<ans;
}