Problem
Você trabalha como gerente e elabora um plano de trabalho para o próximo mês. Cada mês é dividido em T unidades iguais de tempo. Existem n tarefas no total que precisam ser feitas. No entanto, você entende que pode não ser possível concluir todas as tarefas em um mês e deseja fazer um plano ideal escolhendo algumas delas para concluir.
Para cada tarefa, sabemos o tempo ti que precisa ser gasto para concluí-la, bem como o lucro pi< /sub> que a tarefa concluída trará para a empresa. Você deseja planejar algumas tarefas para que:
- O tempo total gasto nas tarefas incluídas no plano não ultrapassou
T.
- O lucro total dessas tarefas foi o máximo.
Faça um plano que tenha as propriedades descritas acima e determine o lucro resultante da implementação desse plano.
Observe que o único plano que corresponde às condições pode não conter nenhuma tarefa.
Dados de entrada
A primeira linha contém os números naturais T (1 ≤ T ≤ 100 000) e n (1 ≤ n &le ; 10) - número de unidades de tempo por mês e número de tarefas.
As n linhas a seguir contêm dois números naturais cada ti e pi (1 <= ti, pi <= 100 000) - tempo para gastar conclua a iésima tarefa e o lucro que pode ser obtido ao concluí-la.
Dados de impressão
Imprimir um único número — o lucro máximo que pode ser obtido com a elaboração de um plano que satisfaça as condições descritas acima.
Exemplos
| # |
Entrada |
Saída |
| 1 |
10 3
8 100
3 10
3 10
| 100 |
| 2 |
10 4
5 10
5 20
25
26 |
31 |