Problem
Trabajas como gerente y elaboras un plan de trabajo para el próximo mes. Cada mes se divide en T unidades de tiempo iguales. Hay n tareas en total que deben realizarse. Sin embargo, entiendes que puede que no sea posible completar todas las tareas en un mes y deseas hacer un plan óptimo eligiendo algunas de ellas para completar.
Para cada tarea, sabemos el tiempo ti que se necesita gastar para completarla, así como la ganancia pi< /sub> que la tarea completada traerá a la empresa. Desea planificar algunas tareas para que:
- El tiempo total dedicado a las tareas incluidas en el plan no superó
T.
- El beneficio total de estas tareas fue el máximo.
Haga un plan que tenga las propiedades descritas anteriormente y determine la utilidad resultante de la implementación de este plan.
Tenga en cuenta que es posible que el único plan que coincida con las condiciones no contenga ninguna tarea.
Ingresar datos
La primera línea contiene los números naturales T (1 ≤ T ≤ 100 000) y n (1 ≤ n &le ; 10) - número de unidades de tiempo por mes y número de tareas.
Las siguientes n líneas contienen dos números naturales, cada ti y pi (1 <= ti, pi <= 100 000) - tiempo para dedicar a completar la tarea iésima y el beneficio que se puede obtener al completarla.
Imprimir datos
Imprimir un solo número — el beneficio máximo que se puede obtener mediante la elaboración de un plan que cumpla con las condiciones escritas anteriormente.
Ejemplos
| # |
Entrada |
Salida |
| 1 |
10 3
8 100
3 10
3 10
| 100 |
| 2 |
10 4
5 10
5 20
25
26 |
31 |