There are $n$ items, numbered from $1$ to $n$. The weight of the item with index $i$ is $a_i$, which is a positive integer.
There is only one available box, which has a maximum weight capacity of $m$, a positive integer. Items are transported in batches, where each batch consists of a subset of the remaining items, until all items have been transported. For each batch, the subset of items is chosen according to the following strategy:
Choose the subset such that the sum of the weights does not exceed $m$ and the number of items is maximized. If there are multiple such subsets with the same maximum number of items, represent each subset as a sequence of item indices sorted in ascending order, and choose the subset whose sequence is lexicographically largest.
Calculate the number of batches required to transport all items using this strategy.
Input
The input is read from standard input.
The input consists of two lines. The first line contains two space-separated positive integers $n$ and $m$. The second line contains $n$ space-separated positive integers, representing the weights $a_i$ of the $n$ items in order.
Output
The output is written to standard output.
Output a single positive integer representing the number of batches required to complete the transport.
Examples
Input 1
11 10 3 1 3 8 4 3 2 1 2 1 1
Output 1
4
Note 1
In the first batch, the maximum number of items that can be transported is $6$, with the index sequence $6, 7, 8, 9, 10, 11$.
In the second batch, the maximum number of items that can be transported is $3$. There are $4$ possible subsets of this size:
- Index sequence $1, 2, 3$.
- Index sequence $1, 2, 5$.
- Index sequence $1, 3, 5$.
- Index sequence $2, 3, 5$.
The lexicographically largest sequence is $2, 3, 5$.
In the third batch, the maximum number of items that can be transported is $1$, with the index sequence $4$.
In the fourth batch, the maximum number of items that can be transported is $1$, with the index sequence $1$.
Input 2
See 2.in and 2.ans in the problem directory.
Input 3
See 3.in and 3.ans in the problem directory.
Subtasks
| Subtask | Score | $n$ | $m$ |
|---|---|---|---|
| 1 | 5 | $n \leq 20$ | $m \leq 100$ |
| 2 | 25 | $n \leq 500$ | $m \leq 10^9$ |
| 3 | 20 | $n \leq 3000$ | $m \leq 10^9$ |
| 4 | 10 | $n \leq 50000$ | $m \leq 10$ |
| 5 | 40 | $n \leq 50000$ | $m \leq 10^9$ |
All data satisfies:
- $1 \leq n \leq 50000, 1 \leq m \leq 10^9$
- The weights of all items satisfy $1 \leq a_i \leq m, i=1 \dots n$
Note
For two distinct sequences $a$ and $b$ of the same length, the lexicographical order is defined as follows: find the first position $i$ where $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 transport schemes, and the comparison between elements refers to the integer comparison of the indices.