E - Loading Cargo onto a Truck Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 433 点

問題文

高橋君は引っ越し業者のアルバイトをしています。倉庫には N 個の荷物があり、i 番目 (1 \leq i \leq N) の荷物の重さは W_i です。

これらの荷物をすべてトラックに積み込んで運ばなければなりません。トラックは必要なだけ何台でも用意でき、各トラックの最大積載量はすべて等しく M です。

荷物の積み込みには以下の条件があります。

  • 各荷物は分割できず、N 個の荷物それぞれをちょうど 1 台のトラックに載せる必要があります。
  • 1 台のトラックに載せた荷物の重さの合計は最大積載量 M 以下でなければなりません。
  • 各トラックによる運搬は 1 回限りです。同じトラックで複数回に分けて運ぶことはできません。

すべての荷物を運ぶために必要なトラックの最小台数を求めてください。

なお、制約 W_i \leq M より各荷物は単体で 1 台のトラックに載せることができるため、必ずすべての荷物を運ぶことができます。

制約

  • 1 \leq N \leq 20
  • 1 \leq M \leq 10^9
  • 1 \leq W_i \leq M (1 \leq i \leq N)
  • 入力はすべて整数である

入力

N M
W_1 W_2 \dots W_N
  • 1 行目には、荷物の個数を表す整数 N と、1 台のトラックの最大積載量を表す整数 M が、スペース区切りで与えられる。
  • 2 行目には、各荷物の重さを表す整数 W_1, W_2, \dots, W_N が、スペース区切りで与えられる。

出力

必要なトラックの台数の最小値を 1 行で出力してください。

入力例 1

4 10
2 5 4 7

出力例 1

2

入力例 2

5 10
6 6 4 4 2

出力例 2

3

入力例 3

10 15
8 7 6 5 4 3 2 9 10 1

出力例 3

4

入力例 4

20 50
24 26 10 40 15 35 5 45 20 30 25 25 12 18 32 8 42 7 13 37

出力例 4

10

入力例 5

1 1000000000
1000000000

出力例 5

1

Score : 433 pts

Problem Statement

Takahashi is working part-time at a moving company. There are N items in the warehouse, and the weight of the i-th item (1 \leq i \leq N) is W_i.

All of these items must be loaded into trucks and transported. We can prepare as many trucks as we need, and each truck has the same maximum capacity of M.

The loading of items must satisfy the following conditions:

  • Each item cannot be divided, and each of the N items must be loaded onto exactly one truck.
  • The total weight of the items loaded onto a single truck must be at most the maximum capacity M.
  • Each truck can make only one trip. It is not possible to make multiple trips with the same truck.

Find the minimum number of trucks required to transport all the items.

Note that because of the constraint W_i \leq M, each item can be loaded onto a truck by itself, so it is always possible to transport all the items.

Constraints

  • 1 \leq N \leq 20
  • 1 \leq M \leq 10^9
  • 1 \leq W_i \leq M (1 \leq i \leq N)
  • All input values are integers.

Input

N M
W_1 W_2 \dots W_N
  • The 1st line contains the integer N, representing the number of items, and the integer M, representing the maximum capacity of a truck, separated by a space.
  • The 2nd line contains the integers W_1, W_2, \dots, W_N, representing the weights of the items, separated by spaces.

Output

Print the minimum number of trucks required in a single line.

Sample Input 1

4 10
2 5 4 7

Sample Output 1

2

Sample Input 2

5 10
6 6 4 4 2

Sample Output 2

3

Sample Input 3

10 15
8 7 6 5 4 3 2 9 10 1

Sample Output 3

4

Sample Input 4

20 50
24 26 10 40 15 35 5 45 20 30 25 25 12 18 32 8 42 7 13 37

Sample Output 4

10

Sample Input 5

1 1000000000
1000000000

Sample Output 5

1