Problem
You work as a manager and draw up a work plan for the next month. Each month is divided into T equal units of time. There are n tasks in total that need to be done. However, you understand that it may not be possible to complete all the tasks in a month and you want to make an optimal plan by choosing some of them to complete.
For each task, we know the time ti that needs to be spent to complete it, as well as the profit pi that the completed task will bring to the company. You want to plan some tasks so that:
- The total time spent on the tasks included in the plan did not exceed
T.
- The total profit from these tasks was the maximum.
Make a plan that has the properties described above and determine the profit resulting from the implementation of this plan.
Please note that the only plan that matches the conditions may not contain any tasks.
Input Data
The first line contains the natural numbers T (1 ≤ T ≤ 100 000) and n (1 ≤ n ≤ 10) - number of time units per month and number of tasks.
The following n lines contain two natural numbers each ti and pi< /code> (1 <= ti, pi <= 100 000) - time to spend to complete the ith task and the profit that can be obtained by completing it.
Imprint data
Print a single number — the maximum profit that can be obtained by drawing up a plan that satisfies the conditions written above.
Examples
| # |
Input |
Output |
| 1 |
10 3
8 100
3 10
3 10
| 100 |
| 2 |
10 4
5 10
5 20
25
26 |
31 |