• 173

## Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

## 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```
Output
`10`

A higher resolution is required to access the IDE