Problem
Lavori come manager e stabilisci un piano di lavoro per il mese successivo. Ogni mese è suddiviso in T unità di tempo uguali. Ci sono n attività in totale che devono essere eseguite. Tuttavia, comprendi che potrebbe non essere possibile completare tutte le attività in un mese e desideri fare un piano ottimale scegliendone alcune da completare.
Per ogni compito, conosciamo il tempo ti che deve essere speso per completarlo, così come il profitto pi< /sub> che l'attività completata porterà all'azienda. Vuoi pianificare alcune attività in modo che:
- Il tempo totale speso per le attività incluse nel piano non ha superato
T.
- Il profitto totale derivante da queste attività è stato il massimo.
Crea un piano che abbia le proprietà sopra descritte e determina il profitto derivante dall'attuazione di questo piano.
Tieni presente che l'unico piano che soddisfa le condizioni potrebbe non contenere alcuna attività.
Inserisci dati
La prima riga contiene i numeri naturali T (1 ≤ T ≤ 100 000) e n (1 ≤ n &le ; 10) - numero di unità di tempo al mese e numero di attività.
Le seguenti n righe contengono due numeri naturali ciascuna ti e pi < /code> (1 <= ti, pi <= 100 000) - tempo da spendere per completare l'iesimo compito e il profitto che si può ottenere completandolo.
Dati editoriali
Stampa un singolo numero — il massimo profitto che si può ottenere elaborando un piano che soddisfi le condizioni sopra scritte.
Esempi
| # |
Input |
Uscita |
| 1 |
10 3
8 100
3 10
3 10
| 100 |
| 2 |
10 4
5 10
5 20
25
26 |
31 |