D. dir -C
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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