Deadline – Regional event 2014

Level 5

Énoncé

Il ne reste plus beaucoup de temps avant la fin de l'épreuve. Afin de maximiser vos chances, vous allez calculer quels sont les exercices à résoudre en priorité.

On vous donne le temps qu'il vous reste avant la fin de l'épreuve, et pour chaque exercice, le nombre de points qu'il rapporte et le temps qu'il vous faudra pour le résoudre. Renvoyez le nombre de points maximum que vous pouvez gagner sans dépasser la limite de temps.

Entrée

  • Sur la première ligne, N, le temps qu'il vous reste.
  • Sur la seconde ligne, M, le nombre d'exercices qu'il vous reste à résoudre.
  • Sur les M lignes suivantes, deux entiers ti et pi séparés par une espace. ti est le temps nécessaire pour résoudre l'exercice i et pi est le nombre de points que vous rapportera cet exercice une fois résolu.

Sortie

En sortie, vous devez afficher le nombre de point que vous pouvez encore gagner avant la fin de l'épreuve.

Contraintes

  • 0 < N <= 2 000
  • 0 < M <= 5 000

Runtime constraints

Maximum memory usage
10000 kilobytes
Maximum execution time
3000 milliseconds

Input/output samples

Sample input
12
8
2 5
3 8
5 14
2 6
4 13
6 17
3 10
1 4
Sample output
38
Sample input
11
5
1 1
2 6
5 18
6 22
7 28
Sample output
40

Submit your solution

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