Laine à vendre – Épreuve régionale 2011

Énoncé¶

Joseph Marchand aime les animaux : en plus du célèbre Scooby-Naire, il a également un mouton de compagnie. Seulement, un mouton en ville, ce n'est pas très pratique et ça coûte cher. Afin de rentabiliser son mouton (n'oublions pas que Joseph Marchand est très radin), il décide de le tondre. Avec la laine qu'il récolte, Joseph Marchand fait du fil de laine, qu'il revend.

Sachant que Joseph Marchand souhaite vendre N mètres de fil de laine et que vous connaissez la table des prix suivant la longueur de fil (vous pouvez utiliser plusieurs valeurs de cette table), écrivez une fonction renvoyant le prix maximum auquel Joseph Marchand peut espérer vendre son fil.

Dans l'exemple 1 ci-dessous, le prix maximum est obtenu en vendant deux fois 10 m de fil et une fois 3 m (on a alors 2 × 30 + 5 = 65).

Entrée¶

• Sur la première ligne, l'entier N correspondant au nombre de mètres de fil de laine.
• Sur la deuxième ligne, l'entier M.
• Sur la ligne suivante, M entiers, séparés d'un espace. Le j-ième entier correspond au prix de j mètres de fil de laine.

Sortie¶

Le prix maximal que Joseph pourra obtenir.

Contraintes¶

• 1 <= N <= 3 000
• 1 <= M <= 3 000