Cow Dance Show.
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 puede soportar vacas bailando simultáneamente. Las vacas en el rebaño están convenientemente numeradas en el orden en que deben aparecer en la danza. Cada vaca planea bailar por una duración específica de tiempo . Inicialmente, aparecen las vacas en el escenario y comienzan a bailar. Cuando la primera de esas vacas completa su parte, ella deja el escenario y la vaca comienza a bailar inmediatamente, y así sucesivamente, por lo tanto siempre hay 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 .
Claramente, cuando más grande sea el valor de , menor el valor de . Como el show no puede durar mucho, a usted se le da como entrada un limite superior especificando el mayor valor posible de . Sujeto a esta restricción, por favor, determine el menor valor posible de .
Entrada
La primera línea de la entrada contiene y , donde es un entero de valor a lo más 1 millón.
Las siguientes líneas dan las duraciones de las partes danzantes para las vacas . Cada valor es un entero en el rango .
Se garantiza que si , el show terminará a tiempo.
Salida
Imprima el menor valor posible de tal que la ejecución de la danza tomará no más de unidades de tiempo.
Ejemplo de Entrada
5 8
4
7
8
6
4
Ejemplo de Salida
4
Comments