← 返回题目列表

AtCoder · awc0023_e

E. 电梯运输

中文机器翻译题面 查看原题

分数: 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