Goal
The rod cutting problem consists of cutting a rod in some pieces of different length, each having a specific value, such that the total value is maximized.
For example, consider that the rods of length 1, 2, 3 and 4 are marketable with respective values 1, 5, 8 and 9.
A rod of length 4 can then be cut in pieces in five different ways:
• 0×1 + 0×2 + 0×3 + 1×4 → total value: 0×1 + 0×5 + 0×8 + 1×9 = 9
• 1×1 + 0×2 + 1×3 + 0×4 → total value: 1×1 + 0×5 + 1×8 + 0×9 = 9
• 0×1 + 2×2 + 0×3 + 0×4 → total value: 0×1 + 2×5 + 0×8 + 0×9 = 10
• 2×1 + 1×2 + 0×3 + 0×4 → total value: 2×1 + 1×5 + 0×8 + 0×9 = 7
• 4×1 + 0×2 + 0×3 + 0×4 → total value: 4×1 + 0×5 + 0×8 + 0×9 = 4
The optimal cut is thus two pieces of length 2 which gives a total value of 10.
You can make pieces that are not marketable, but theses pieces will have a value of 0.
The rod cutting problem is the one-dimensional variant of the cutting stock problem. https://en.wikipedia.org/wiki/Cutting_stock_problem
Input
First line: L the length of the rod
Second line: N the number of different pieces that are marketable.
Next N lines: length value of each marketable piece, separated by a space.
Output
The maximum total value that can be obtained from the cut of the rod in different pieces.
Constraints
0 < L ≤ 100 000
0 < N < 50
0 < length ≤ 10 000 000 000
0 ≤ value
Example
Input
4
4
1 1
2 5
3 8
4 9
