# dir -C

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.

We split list of filenames into several continuous blocks such as all blocks except for maybe last one consist of l filenames, and last block consists of no more than l filenames, then blocks are printed as columns. Width of each column wi is defined as maximal length of the filename in appropriate block. Columns are separated by 1 × l column of spaces. So, width of the output is calculated as , i.e. sum of widths of each column plus number of columns minus one. Example of multi-column output:

a       accd e t
aba     b    f wtrt
abacaba db   k

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.

# 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.

# Examples

input

11 20
1 3 7 4 1 2 1 1 1 1 4

output

3

# Solution

# 思路

从小到大枚举行数，使用RMQ维护连续区间最大值累加，找到可行方案即输出。 注意其不满足二分使用条件。

# Code

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 1e5 + 10;
int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || '9' < ch)
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while ('0' <= ch && ch <= '9')
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
int n, m, a[N];

int f[N][20];
void rmq_init()
{
    for (int i = 0; i < n; i++) {  
        f[i][0] = a[i]; 
    }  
    for (int j = 1; (1 << j) <= n; j++)
        for (int i = 0; i + (1 << j) <= n; i++)
        {
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
            if (i + 1 + (1 << j) > n)
                f[i + 1][j] = f[i][j];
        }
}
int st(int u, int v)
{ 
    int k = (int)log2((v > n ? n : v) - u + 1.0);
    return max(f[u][k], f[(v > n ? n : v) - (1 << k) + 1][k]);
}
bool check(int x)
{
    if (x == n)
        return true;
    int sum = 0;
    int l = 0;
    while (l < n)
    {
        sum += st(l, l + x - 1) + 1;
        if (sum > m)
        {
            return false;
        }
        l += x;
    }
    return true;
}
void readin()
{
    n = read();
    m = read() + 1;
    for (int i = 0; i < n; ++i)
        a[i] = read();
}
void solve()
{
    memset(f, 0, sizeof(f));  
    rmq_init();
    for (int i = 1; i <= n; ++i)
        if (check(i))
        {
            printf("%d\n", i);
            return;
        }
}
int main()
{
    readin();
    solve();
    return 0;
}