Famous Berland coder and IT manager Linus Gates announced his next proprietary open-source system "Winux 10.04 LTS"
In this system command "_dir -C_" prints list of all files in the current catalog in multicolumn mode.
Lets define the multicolumn mode for number of lines l. Assume that filenames are already sorted lexicographically.
Example of multi-column output:
In the example above width of output is equal to 19.
"_dir -C_" command selects minimal l, such that width of the output does not exceed width of screen w.
Given information about filename lengths and width of screen, calculate number of lines l printed by "_dir -C_" command.
First line of the input contains two integers n and w — number of files in the list and width of screen (1 ≤ n ≤ 105, 1 ≤ w ≤ 109).
Second line contains n integers fi — lengths of filenames. i-th of those integers represents length of i-th filename in the lexicographically ordered list (1 ≤ fi ≤ w).
Print one integer — number of lines l, printed by "_dir -C_" command.
## Input
First line of the input contains two integers n and w — number of files in the list and width of screen (1 ≤ n ≤ 105, 1 ≤ w ≤ 109).Second line contains n integers fi — lengths of filenames. i-th of those integers represents length of i-th filename in the lexicographically ordered list (1 ≤ fi ≤ w).
## Output
Print one integer — number of lines l, printed by "_dir -C_" command.
[samples]
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of files.
Let $ w \in \mathbb{Z}^+ $ be the screen width.
Let $ f = (f_1, f_2, \dots, f_n) $ be a sequence of positive integers representing the lengths of filenames in lexicographic order, where $ 1 \le f_i \le w $.
Let $ l \in \mathbb{Z}^+ $ be the number of lines in multicolumn output.
Let $ c = \lceil n / l \rceil $ be the number of columns.
The width of the output is defined as:
$$
\text{width}(l) = (c - 1) \cdot \min_{i \in \{1, \dots, c\}} \left( \max_{j \in \{1, \dots, l\}} f_{(j-1)c + i} \right) + \max_{j \in \{1, \dots, l\}} f_{(j-1)c + c}
$$
But more precisely, in standard multicolumn layout:
The maximum width is the sum of the maximum filename length in each column, plus $ c - 1 $ spaces between columns.
Actually, standard model:
- The output has $ l $ rows and $ c = \lceil n / l \rceil $ columns.
- The $ j $-th column contains filenames from index $ (j-1)l + 1 $ to $ \min(jl, n) $.
- The width of column $ j $ is $ \max \{ f_i \mid i \in \text{column } j \} $.
- Total width = sum of column widths + $ (c - 1) $ spaces between them.
So:
Let $ c = \lceil n / l \rceil $.
For $ j = 1 $ to $ c $:
Let $ \text{col}_j = \max \{ f_i \mid (j-1)l < i \le \min(jl, n) \} $.
Then:
$$
\text{width}(l) = \sum_{j=1}^{c} \text{col}_j + (c - 1)
$$
**Constraints**
1. $ 1 \le n \le 10^5 $
2. $ 1 \le w \le 10^9 $
3. $ 1 \le f_i \le w $ for all $ i \in \{1, \dots, n\} $
**Objective**
Find the minimal $ l \in \{1, 2, \dots, n\} $ such that:
$$
\sum_{j=1}^{\lceil n/l \rceil} \max_{i \in I_j} f_i + \left( \left\lceil \frac{n}{l} \right\rceil - 1 \right) \le w
$$
where $ I_j = \{ (j-1)l + 1, \dots, \min(jl, n) \} $.