Manhattan maboul – Qualification 2019

Niveau 3

Énoncé

Ah Manhattan… Le quartier préféré de Haruhi ! Nombreux de ses amis sont d'ailleurs de passage à New-York et Haruhi aimerait les revoir depuis son dernier long voyage.

Adepte des finales Prologin, Haruhi a pour objectif de rencontrer en $M$ jours consécutifs un nombre maximal de ses amis. Pour cela elle a noté l'arrivée de tout le monde. À noter qu'il est possible que plusieurs amis soient présents un même jour.

Entrée

La première ligne contient deux entiers $N$ et $M$ correspondant respectivement au nombre d'amis passant par New-York, ainsi qu'au nombre de jours consécutifs que Haruhi peut utiliser pour rencontrer ses amis.

Sur la ligne suivante $N$ entiers, représentant un jour où un des amis de Haruhi est à Manhattan.

Sortie

Le nombre d'amis maximum que Haruhi peut revoir en $M$ jours consécutifs.

Contraintes

  • $1 \le N \le 100$
  • $1 \le M \le 36$
  • $1 \le jour \le 10^6$

Contraintes de performance

  • $1 \le N \le 10^6$
  • $1 \le M \le 10^5$

Contraintes d'exécution

Utilisation mémoire maximum
20000 kilo-octets
Temps d'exécution maximum
600 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
6 5
3 11 1 7 6 12
Exemple de sortie
3
Commentaire

Haruhi peut rencontrer 3 de ses amis en 5 jours consécutifs.

Exemple d'entrée
5 2
4 1 7 9 7
Exemple de sortie
3
Commentaire

Dans le meilleur des cas, Haruhi peut croiser 3 de ses amis en 2 jours consécutifs en sélectionnant les 3 derniers de la liste.