Cow Dance Show.


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 128M

Author:
Problem type
Allowed languages
C, C++, Java, Pascal, Python, VB

Después de varios meses de ensayo, las vacas están apenas listas para poner su presentación anual de danza; este año ellas van a ejecutar el famoso ballet bovino "Cowpelia".

El único aspecto del show que falta determinar es el tamaño del escenario. Un escenario de tamaño K puede soportar K vacas bailando simultáneamente. Las N vacas en el rebaño (1 \leq N \leq 10,000) están convenientemente numeradas 1...N en el orden en que deben aparecer en la danza. Cada vaca i planea bailar por una duración específica de tiempo d_i. Inicialmente, aparecen las vacas 1...K en el escenario y comienzan a bailar. Cuando la primera de esas vacas completa su parte, ella deja el escenario y la vaca K+1 comienza a bailar inmediatamente, y así sucesivamente, por lo tanto siempre hay K vacas bailando (hasta el final del show, cuando comenzamos a quedarnos sin vacas). El show se termina cuando la última vaca termina su parte de baile, en el tiempo T.

Claramente, cuando más grande sea el valor de K, menor el valor de T. Como el show no puede durar mucho, a usted se le da como entrada un limite superior T_{max} especificando el mayor valor posible de T. Sujeto a esta restricción, por favor, determine el menor valor posible de K.

Entrada

La primera línea de la entrada contiene N y T_{max}, donde T_{max} es un entero de valor a lo más 1 millón.

Las siguientes N líneas dan las duraciones d_1 ... d_N de las partes danzantes para las vacas 1...N. Cada valor d_i es un entero en el rango 1...100,000.

Se garantiza que si K=N, el show terminará a tiempo.

Salida

Imprima el menor valor posible de K tal que la ejecución de la danza tomará no más de T_{max} unidades de tiempo.

Ejemplo de Entrada

5 8    
4
7
8
6     
4

Ejemplo de Salida

4

Comments

There are no comments at the moment.