Flow Layout

A flow layout manager places rectangular objects into a rectangular window, filling each row from left to right. When the next rectangle does not fit in the remaining space of the current row, it is moved entirely below all rectangles placed so far, starting at the left edge of a new row, and the left-to-right filling continues from there.

Given the dimensions of several rectangles and the maximum width of the window, compute the dimensions of the final window after every rectangle has been placed.

The width of the window equals the width of its widest row (the sum of the widths of the rectangles in that row), and the height of the window equals the sum of the row heights, where each row's height is the tallest rectangle in that row.

For example, with a window at most 35 units wide and three rectangles measuring 10 x 5, 20 x 12, and 8 x 13, the first two rectangles share the first row (10 + 20 = 30 ≤ 35) while the third starts a second row (30 + 8 = 38 > 35). The final window is 30 x 25, because its width is 10 + 20 = 30 and its height is 12 + 13 = 25.

The input consists of one or more data sets, followed by a final line containing only the value 0.

Each data set begins with a line containing an integer m ($1 \le m \le 80$), the maximum width of the window. It is followed by at least one and at most 15 lines, each giving the dimensions of one rectangle: its width first, then its height. The list of rectangles ends with the pair -1 -1, which is not an actual rectangle.

Each rectangle is between 1 and 80 units wide (inclusive) and between 1 and 100 units high (inclusive).

For each data set, print the width of the resulting window, a space, the lowercase letter x, a space, and then the height of the resulting window.