Problem Description

There are $n$ items, numbered from $1$ to $n$. The weight of item $i$ is denoted by $a_i$, which is a positive integer.

There is only one available box, and its maximum capacity is a positive integer $m$. The items are moved in batches. In each batch, some of the remaining items are moved away, until all items have been moved. The items moved in each batch form a subset of the items remaining at that time, chosen by the following strategy:

Choose a plan such that the total weight does not exceed $m$ and the number of included items is as large as possible. If there are multiple plans with the maximum number of items, then sort the chosen item indices in increasing order into a sequence, and choose the plan whose sequence is lexicographically largest.

Compute how many batches will be needed under this strategy.

Input Format

The input has two lines. The first line contains two positive integers $n, m$ separated by spaces. The second line contains $n$ positive integers separated by spaces, which are the weights $a_i$ of the $n$ items in order.

Output Format

Output one positive integer, representing the number of batches required to finish moving.

11 10
3 1 3 8 4 3 2 1 2 1 1

4

见附件中的 2.in。

见附件中的 2.ans。

见附件中的 3.in。

见附件中的 3.ans。

Hint

[Sample Explanation #1]

In the first batch, at most $6$ items can be moved, and the index sequence is $6, 7, 8, 9, 10, 11$.

In the second batch, at most $3$ items can be moved. At this time there are $4$ different plans with the maximum number of items:

• Index sequence $1, 2, 3$.
• Index sequence $1, 2, 5$.
• Index sequence $1, 3, 5$.
• Index sequence $2, 3, 5$.

Choose the lexicographically largest one, $2, 3, 5$.

In the third batch, at most $1$ item can be moved, and the index sequence is $4$.

In the fourth batch, at most $1$ item can be moved, and the index sequence is $1$.

[Subtasks]

All testdata satisfies:

• $1 \leq n \leq 50000$, $1 \leq m \leq 10^9$;
• For all item weights, $1 \leq a_i \leq m$, $i=1 \dots n$.

[Notes]

For two sequences $a$ and $b$ of the same length that are not identical, if the elements in the sequences can be compared, then the lexicographical order between $a$ and $b$ is defined as follows: scan from left to right to find the first position $i$ such that $a_i \neq b_i$. If $a_i < b_i$, then $a<b$; otherwise, if $a_i>b_i$, then $a>b$.

In this problem, $a$ and $b$ are the sequences of item indices involved in two moving plans, and comparing elements means comparing the indices as integers.

Problem License

From the Tsinghua University 2021 National Outstanding High School Students Informatics Experience Camp (THUSC 2021).

In the following, “this repository” refers to the official THUSC 2021 repository (https://gitlink.org.cn/thusaa/thusc2021).

1. Any organization or individual may use or redistribute the problems in this repository for free.
2. When using the problems in this repository, any organization or individual should do so free of charge and publicly. It is strictly forbidden to use these problems for profit or to add special access restrictions to these problems.
3. If possible, please provide methods to obtain resources such as testdata, reference solutions, and editorials when using the problems in this repository; otherwise, please attach the link to this repository.
4. The Department of Computer Science, Tsinghua University reserves all rights.

Translated by ChatGPT 5