装箱问题的近似算法First Fit Decreasing

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

设有体积分别为v1 ,v2 , ……,vn 的n 种物品要装入容量为c 的箱子里。不同的装箱方案所需的箱子数可能不同。装箱问题要求找出一种装完这n种物品所需的箱子数最少的装箱方案。装箱问题的近似算法First Fit Decreasing的基本思想是,先将n个物品依其体积从大到小排序 v1 ≤v2 ≤……≤ vn ,然后用算法First Fit求解。
设计并实现装箱问题的近似算法First Fit Decreasing。

Input

输入数据的第一行有2 个正整数n和c(n<1000000,c<=100),分别表示有n种物品要装入容量为c的箱子里。接下来的1行中,有n个正整数分别表示n种物品的体积。

Output

将计算出的最少箱子数输出。

Sample Input

10 6
3 4 4 3 5 1 2 5 3 1

Sample Output

6

Hint

Source