Problem
Vous travaillez en tant que manager et établissez un plan de travail pour le mois suivant. Chaque mois est divisé en T unités de temps égales. Il y a n tâches au total qui doivent être effectuées. Cependant, vous comprenez qu'il peut ne pas être possible d'accomplir toutes les tâches en un mois et vous souhaitez établir un plan optimal en choisissant certaines d'entre elles à accomplir.
Pour chaque tâche, nous connaissons le temps ti qu'il faut passer pour l'accomplir, ainsi que le profit pi< /sub> que la tâche terminée apportera à l'entreprise. Vous souhaitez planifier certaines tâches afin que :
- Le temps total consacré aux tâches incluses dans le plan n'a pas dépassé
T.
- Le profit total de ces tâches était le maximum.
Faites un plan qui a les propriétés décrites ci-dessus et déterminez le profit résultant de la mise en œuvre de ce plan.
Veuillez noter que le seul plan qui correspond aux conditions peut ne contenir aucune tâche.
Données d'entrée
La première ligne contient les nombres naturels T (1 ≤ T ≤ 100 000) et n (1 ≤ n &le ; 10) - nombre d'unités de temps par mois et nombre de tâches.
Les lignes n suivantes contiennent deux nombres naturels chacun ti et pi < /code> (1 <= ti, pi <= 100 000) - temps à consacrer à terminez la ième tâche et le profit qui peut être obtenu en la complétant.
Impression données
Imprimer un seul numéro — le profit maximum qui peut être obtenu en établissant un plan qui satisfait aux conditions écrites ci-dessus.
Exemples
| # |
Entrée |
Sortie |
| 1 |
10 3
8 100
3 10
3 10
| 100 |
| 2 |
10 4
5 10
5 20
25
26 |
31 |