Bouts de bois – Épreuve régionale 2017

Niveau 3

Énoncé

Ce matin Joseph Marchand est allé ramasser des bouts de bois dans la forêt. De retour chez lui il essaie de les assembler pour construire des rectangles en les accrochant par groupes de 4.

Un rectangle peut être réalisé avec 2 paires de 2 bouts de bois de même longueur. Par exemple, il est possible de faire un rectangle avec des bouts de bois de longueur 2, 2, 3 et 3. Mais ce n'est pas possible avec des bouts de bois de longueur 4, 5, 5 et 5.

Les bouts de bois sont très résistants, mais Joseph dispose d'un outil qui permet d'en diminuer la taille de 1. En revanche, cette opération ne peut être effectuée plus de $K$ fois par bout de bois.

Joseph dispose de $N$ bouts de bois et souhaite construire des rectangles de manière à maximiser la somme de leurs aires.

Aidez Joseph en déterminant la somme des aires rectangles maximales qu'il peut obtenir.

Entrée

L'entrée comprendra deux lignes :

  • La première ligne contiendra deux entiers $N$ et $K$, le nombre de bouts de bois ramassés par Joseph et le nombre de coupes qu'il peut réaliser sur un bout de bois.
  • La deuxième ligne contiendra $N$ nombres, le i-ème d'entre eux $l_i$ étant la taille du i-ème bout de bois

Sortie

Vous afficherez un entier, la somme des aires maximale qu'il est possible d'obtenir.

Contraintes

  • $1 \le N \le 1\ 000$
  • $1 \le K \le 10$
  • $1 \le l_i \le 100$

Contraintes d'exécution

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

Exemples d'entrée/sortie

Exemple d'entrée
4 1
4 2 2 5
Exemple de sortie
8
Commentaire

Sur cet exemple, on coupe le bout de bois de taille 5 pour qu'il ne soit plus que de taille 4. On peut alors créer un rectangle de côtés 2 et 4, donc d'aire 8.

Exemple d'entrée
4 2
2 8 5 3
Exemple de sortie
0
Commentaire

Pour cet exemple, il n'est pas possible de construire de rectangle.

Exemple d'entrée
6 3
2 5 3 7 8 6
Exemple de sortie
35