Lo spettacolo di danza delle mucche#10547
Dopo diversi mesi di prove, le mucche sono ormai quasi pronte a presentare il loro spettacolo di danza annuale. Quest'anno si esibiranno nel famoso balletto bovino «Cowpelia».
L'unica cosa che resta da stabilire per lo spettacolo è la dimensione del palco. Un palco di dimensione può ospitare contemporaneamente mucche danzanti. Le mucche della mandria sono numerate con i numeri 1, \ldots, n nell'ordine in cui devono salire sul palco. Ogni mucca prevede di danzare per un intervallo di tempo di durata .
Inizialmente le mucche 1, \ldots, k salgono sul palco e iniziano a danzare. Quando la prima di queste mucche termina la propria parte, lascia il palco, e la mucca k + 1 inizia immediatamente a danzare. Questo processo continua, in modo che sul palco danzino sempre contemporaneamente mucche (fino alla fine dello spettacolo, quando il numero di mucche rimanenti diventa inferiore a ).
Lo spettacolo termina quando l'ultima mucca finisce la propria parte di danza, al momento .
È evidente che maggiore è il valore di , minore è il valore di . Poiché lo spettacolo non deve durare troppo a lungo, vi viene assegnato un limite T_{\max} sulla sua durata. Con tale limite, determinate il valore minimo possibile di .
La prima riga contiene n~(1 \le n \le 10000) e T_{\max}, dove T_{\max} è un numero intero che non supera 10^6.
Nelle righe successive sono contenute le durate d(1), \ldots, d(n) delle parti di danza delle mucche 1, \ldots, n rispettivamente. Ogni valore è un numero intero compreso nell'intervallo 1, \ldots, 10^5.
È garantito che, per k = n, lo spettacolo termina entro il limite di tempo stabilito.
Stampate il valore minimo possibile di per cui lo spettacolo di danza dura non più di T_{\max} unità di tempo.
Esempio 1