Paragraph#803
In the paragraph, there are blocks of varying heights (for example, regular words and mathematical symbols). Since the paragraph is long, it needs to be divided into lines. The height of each line is determined by the tallest block in it. The height of the paragraph is the sum of the heights of all the lines. The length of each line is equal to the total width of the blocks in that line (spaces are not considered). A block cannot be split between lines, nor can the order of the blocks be changed. Find a way to divide the paragraph into lines so that the total height of the paragraph is minimized. The width and height of each block (, ) and the maximum allowed line length are given in the input.
The first line contains two numbers: (the maximum allowed line length) and (the number of blocks in the paragraph), where 5 \leq N \leq 5000. The next lines each contain two numbers (the width and height of a block).
All sizes are natural numbers not exceeding 10^6. It is guaranteed for all blocks that w(i) \leq TW.
On the first line, print the minimum height of the paragraph. On the second line, print the number of lines needed to divide the paragraph, and in the next lines, print the number of blocks in each corresponding line of the paragraph.
Example 1