L'essenza di un fiore raro è molto ricercata tra i profumieri. Il prezzo di mercato viene fissato giornalmente dal CGE, il Consorzio dei Grossisti di Essenze. Inoltre, essendo di natura organica, l'essenza acquistata da un profumiere deperisce dopo un certo periodo e quindi può essere rivenduta so
*soltanto entro K giorni dall'acquisto (data di scadenza).
*Un profumiere è venuto a conoscenza del prezzo di mercato dell'essenza che il CGE prevede per i prossimi N giorni (N ≥ K), per semplicità numerati da 1 a N. Ritenendo molto affidabili le previsioni del CGE, il profumiere intende comprare una certa quantità di essenza il giorno i per rivenderla il giorno j, tenendo presente però che non può andare oltre la data di scadenza (quindi deve essere i ≤ j
*(quindi deve essere i ≤ j ≤ i+K). Il profumiere intende fare un solo acquisto e una sola vendita successiva all'acquisto.
*Aiutate il profumiere a calcolare il massimo guadagno che può ottenere, calcolato come la differenza tra il prezzo dell'essenza al giorno j e quello al giorno i. Notate che è permesso scegliere j=i: in questo modo, anche se il prezzo di mercato dell'essenza fosse in discesa per tutto il periodo considerato, sarebbe possibile evitare perdite.
*Dati di input
Il file input.txt è composto da due righe.
La prima riga contiene due interi positivi separati da uno spazio, rispettivamente il numero K di giorni per la data di scadenza e il numero N di prossimi giorni.
La seconda riga contiene N interi positivi separati da uno spazio, i quali rappresentano il prezzo di vendita dell'essenza nei prossimi N giorni.
*Dati di output
Il file output.txt è composto da una sola riga contenente un intero che rappresenta il massimo guadagno del profumiere, con le regole descritte sopra.
Assunzioni
1 ≤ N ≤ 1000,
1 ≤ K ≤ N .
*Esempi di input/output
File input.txt File output.txt
2 6
3 6 2 6 9 6
7
Nota/e
Un programma che restituisce sempre lo stesso valore, indipendentemente dai dati in input.txt, non totalizza alcun punteggio in aggiunta a quello ottenuto per la sua compilazione
Qualcuno può darmi una mano?