Choisir ses cours

L'école où vous étudiez est très libre : vous pouvez choisir les cours auxquels vous vous rendez. Dans une journée, N cours se succèdent. La seule contrainte est que vous devez obligatoirement assister à au moins M cours.

Chacun de ces cours vous rapporte un certain nombre de points P pour le diplôme délivré par votre école. Etant quelqu'un de très fainéant, vous désirez vous rendre à un minimum de cours (donc à M cours), et vous souhaitez aussi que ces cours se suivent afin de ne pas perdre de temps à attendre au milieu de votre journée. Mais comme vous êtes en plus quelqu'un de malin, vous voulez également que ces cours vous rapportent un maximum de points pour le diplôme.

Étant donné la liste des cours et des points qu'ils rapportent respectivement, déterminez le nombre maximal de point que vous pourrez obtenir pour votre diplôme en vous fatiguant un minimum.

• 2 <= N <= 100 000, où N est le nombre total de cours.
• 1 <= M <= N, où M est le nombre de cours auxquels vous devez assister.
• 1 <= P <= 1 000, où P est le nombre de points que rapporte un cours.

Pour 50% des tests, 2 <= N <= 2 000.

• La première ligne de l'entrée contient deux entiers séparés par un espace : le nombre total N de cours, et le nombre M de cours consécutifs auxquels vous devez assister.
• Les N lignes suivantes de l'entrée contiennent chacune un entier : le i-ème de ces entiers représente le nombre de point rapporté par le i-ème cours de la journée.

Vous devez simplement afficher un entier sur la sortie : le nombre maximal de points que peuvent vous rapporter M cours consécutifs.

Les cours les plus avantageux sont les quatre derniers cours de la journée.

Nous vous proposons des indications pour lire l'entrée et afficher la sortie, en C++ et Caml, afin que vous ne risquiez pas d'être bloqué là-dessus. Il n'est pas du tout obligatoire de les utiliser.

Lecture de l'entrée en C/C++

Utilisez simplement scanf("%d", &nomVariable); pour lire un entier sur l'entrée et le stocker dans la variable nomVariable. Pensez à ajouter #include <stdio.h> en haut de votre fichier.

Lecture de l'entrée en Caml

Ajoutez la ligne suivante au début de votre fichier :

let read_int () = Scanf.scanf " %d" (fun t -> t)

Utilisez alors read_int() à chaque fois que vous souhaitez lire un entier sur l'entrée.