Corsa#10152
La mucca Bessie vuole diventare un'atleta più forte, quindi ha deciso di correre lungo una pista per esattamente minuti. Durante ogni minuto, può correre oppure riposare per l'intero minuto.
La distanza totale che Bessie può percorrere dipende dal suo coefficiente di stanchezza, che inizialmente è pari a . Se Bessie corre durante il minuto , percorre una distanza d_i e il suo coefficiente di stanchezza aumenta di . Il coefficiente di stanchezza non può mai superare .
Se Bessie riposa, il suo coefficiente di stanchezza diminuisce di , ma non può diventare negativo. Bessie può ricominciare a correre solo quando il suo coefficiente di stanchezza raggiunge . In quel momento può scegliere: correre oppure continuare a riposare.
Alla fine dell'allenamento di minuti, il coefficiente di stanchezza di Bessie deve essere esattamente ; altrimenti non le resterà abbastanza energia per il resto della giornata.
Trova la distanza totale massima che Bessie può percorrere rispettando tutte queste regole.
Nella prima riga si trovano due numeri interi n~(1 \le n \le 10^4) e m~(1 \le m \le 500).
Le successive righe contengono i numeri interi d_1, d_2, \ldots, d_n~(1 \le d_i \le 1000), dove d_i — è la distanza che Bessie percorre se decide di correre durante il minuto .
Stampa un singolo numero intero: la distanza totale massima che Bessie può percorrere rispettando tutte le regole date.
Esempio 1