Deadline – Regional event 2014

É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 t_i et p_i séparés par une espace. t_i est le temps nécessaire pour résoudre l'exercice i et p_i 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