分数: 433 分
问题陈述
高桥在一家搬家公司做兼职。今天的任务是运输 N 包来自 1使用电梯从公寓楼的第 3 层到单个目标楼层。
每包 i (1 \leq i \leq N) 的权重为 W_i 公斤。该公寓楼的电梯最大总重量为 C 公斤为一次装载的包裹。高桥乘坐电梯并肩运送包裹,但他自己的体重不计入承重范围内。
为了高效地完成工作,高桥决定将 N 打包成几组并使用电梯将每组一起运输。这里,每个包恰好属于一个组,并且每个组至少包含一个包。另外,每组包裹的总重量不得超过 C 公斤。
在一次行程中,高桥将属于一组的所有包裹装载到电梯上,并将它们从 1st 楼层至目的楼层。为了运送下一批人,高桥返回 1楼,电梯空着。行程次数等于组数。
求运输所有包裹所需的最少行程次数。
注意,保证每个包裹的重量最多为 C,因此任何单个包裹都可以单独运输。
约束
- 1 \leq N \leq 15
- 1 \leq C \leq 10^9
- 1 \leq W_i \leq C (1 \leq i \leq N)
- 所有输入均为整数
输入
N C W_1 W_2 \ldots W_N
- 第一行包含包裹数量 N 和电梯的载重能力 C,用空格分隔。
- 第二行包含每个包裹的重量 W_1, W_2, \ldots, W_N,用空格分隔。
输出
在一行上打印运输所有包裹所需的最少行程数。
示例输入 1
3 10 4 5 6
示例输出 1
2
示例输入 2
5 100 30 50 40 20 60
示例输出 2
2
示例输入 3
8 1000 200 300 150 400 250 100 350 450
示例输出 3
3