A - Organizing the Bookshelf Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

高橋君は本棚に本を並べようとしています。本棚には第 1 段、第 2 段、…、第 N 段の N 個の段があり、各段の横幅はすべて W センチメートルです。はじめ、すべての段は空です。

本棚に並べる本は N 冊あり、i 番目 (1 \leq i \leq N) の本の厚さは L_i センチメートルです。各本の厚さは W 以下であることが保証されているため、どの本も単体では必ず 1 つの段に収まります。

ある段に k 冊 (k \geq 1) の本（厚さ a_1, a_2, \ldots, a_k）が左から順に並んでいるとき、その段で使用されている幅を (a_1 + a_2 + \cdots + a_k) + (k - 1) センチメートルと定めます。これは、隣り合う本どうしの間に必ず 1 センチメートルの隙間を設けることに対応します。例えば、1 冊だけ置かれている段の使用幅はその本の厚さに等しく、1 冊も本が置かれていない段の使用幅は 0 センチメートルです。

高橋君は 1 番目の本から N 番目の本まで、番号の小さい順に 1 冊ずつ以下のルールに従って配置していきます。「現在の段」は最初は第 1 段です。i 番目の本を配置するとき：

  1. 現在の段に 1 冊も本が置かれていない場合、現在の段の左端から i 番目の本を配置します。現在の段は変わりません。
  2. 現在の段にすでに本があり、使用されている幅が S センチメートルであるとします。
  • S + 1 + L_i \leq W ならば、既に置かれている本の右側に 1 センチメートルの隙間を空けて、i 番目の本を現在の段に続けて配置します。現在の段は変わりません。
  • S + 1 + L_i > W ならば、i 番目の本は現在の段に収まりません。現在の段の次の段（番号が 1 大きい段）を新たな「現在の段」とします。番号の小さい段から順に埋めていくため、この新たな段は必ず空です。その段の左端から i 番目の本を配置します。

すべての N 冊の本を並べ終えたとき、本が 1 冊以上置かれている段の数は全部で何段になるかを求めてください。

制約

  • 1 \leq N \leq 10^6
  • 1 \leq W \leq 10^9
  • 1 \leq L_i \leq W (1 \leq i \leq N)
  • 入力はすべて整数である。

入力

N W
L_1 L_2 \ldots L_N
  • 1 行目には、本の冊数を表す整数 N と、本棚の各段の横幅を表す整数 W が、スペース区切りで与えられる。
  • 2 行目には、各本の厚さを表す整数 L_1, L_2, \ldots, L_N が、スペース区切りで与えられる。

出力

本が 1 冊以上置かれている段の数を 1 行で出力してください。

入力例 1

5 10
3 4 2 5 3

出力例 1

3

入力例 2

8 15
5 5 5 5 5 5 5 5

出力例 2

4

入力例 3

10 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

出力例 3

10

Score : 266 pts

Problem Statement

Takahashi is arranging books on a bookshelf. The bookshelf has N shelves: shelf 1, shelf 2, …, shelf N, and each shelf has a width of W centimeters. Initially, all shelves are empty.

There are N books to arrange on the bookshelf, and the i-th book (1 \leq i \leq N) has a thickness of L_i centimeters. It is guaranteed that the thickness of each book is at most W, so every book can individually fit on a single shelf.

When k (k \geq 1) books (with thicknesses a_1, a_2, \ldots, a_k) are lined up from left to right on a shelf, the used width of that shelf is defined as (a_1 + a_2 + \cdots + a_k) + (k - 1) centimeters. This corresponds to always leaving a 1-centimeter gap between adjacent books. For example, the used width of a shelf with only one book equals the thickness of that book, and the used width of a shelf with no books is 0 centimeters.

Takahashi places the books one by one in order from the 1-st book to the N-th book, following the rules below. The "current shelf" is initially shelf 1. When placing the i-th book:

  1. If no books are currently placed on the current shelf, place the i-th book starting from the left end of the current shelf. The current shelf does not change.
  2. Suppose books are already on the current shelf, and the used width is S centimeters.
  • If S + 1 + L_i \leq W, place the i-th book on the current shelf to the right of the already placed books, leaving a 1-centimeter gap. The current shelf does not change.
  • If S + 1 + L_i > W, the i-th book does not fit on the current shelf. The shelf after the current shelf (the shelf with the number one greater) becomes the new "current shelf." Since shelves are filled in order from the smallest number, this new shelf is always empty. Place the i-th book starting from the left end of that shelf.

After all N books have been arranged, determine the total number of shelves that have at least one book placed on them.

Constraints

  • 1 \leq N \leq 10^6
  • 1 \leq W \leq 10^9
  • 1 \leq L_i \leq W (1 \leq i \leq N)
  • All input values are integers.

Input

N W
L_1 L_2 \ldots L_N
  • The first line contains an integer N representing the number of books and an integer W representing the width of each shelf, separated by a space.
  • The second line contains integers L_1, L_2, \ldots, L_N representing the thickness of each book, separated by spaces.

Output

Print the number of shelves that have at least one book placed on them, in a single line.

Sample Input 1

5 10
3 4 2 5 3

Sample Output 1

3

Sample Input 2

8 15
5 5 5 5 5 5 5 5

Sample Output 2

4

Sample Input 3

10 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

10