Laine à vendre – Regional event 2011

Level 4

É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

Runtime constraints

Maximum memory usage
2048 kilobytes
Maximum execution time
800 milliseconds

Input/output samples

Sample input
23
10
1 4 5 7 9 13 17 17 23 30
Sample output
65
Sample input
10
10
1 2 3 4 14 6 21 8 9 10
Sample output
28

Submit your solution

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