Paragraph
In the paragraph, there are blocks of varying heights, such as regular words and mathematical symbols. Since the paragraph is lengthy, it needs to be divided into lines. The height of each line is determined by the tallest block within it. The overall height of the paragraph is the sum of the heights of all the lines. The length of a line is defined by the total width of the blocks it contains (spaces are not considered). Blocks cannot be split between lines, nor can their order be changed. Your task is to divide the paragraph into lines such that the total height of the paragraph is minimized. The input provides the width and height of each block (w(i), h(i)) and the maximum allowable line length TW.
Input
The first line contains two numbers: TW (the maximum allowable line length) and N (the number of blocks in the paragraph), where 5 ≤ N ≤ 5000. The next N lines each contain two numbers representing the width and height of a block.
All dimensions are natural numbers not exceeding 10^6. It is guaranteed that for all blocks, w(i) ≤ TW.
Output
On the first line, output the minimum height of the paragraph. On the second line, output the number of lines M into which the paragraph should be divided. In the following M lines, output the number of blocks in each corresponding line of the paragraph.