Bouts de bois – Regional event 2017

Level 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$

Runtime constraints

Maximum memory usage
1000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
4 1
4 2 2 5
Sample output
8
Note

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.

Sample input
4 2
2 8 5 3
Sample output
0
Note

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

Sample input
6 3
2 5 3 7 8 6
Sample output
35

Submit your solution

You have to register or log in to be able to submit your solution.