问题描述

流式布局管理器将矩形对象从左到右放置在一个矩形窗口中。如果某一行中没有足够的空间放置一个对象，那么该对象会被完全放置在第一行所有对象的下方，并且从左边缘开始继续从左到右排列。给定一组矩形的尺寸和一个窗口的最大宽度，你需要编写一个程序来计算所有矩形放置后的最终窗口的尺寸。

例如，给定一个最大宽度为 35 单位的窗口，以及三个尺寸分别为 10x5、20x12 和 8x13 的矩形，流式布局管理器在添加每个矩形后会创建一个窗口，其外观如下（此处为示意图，实际输出为尺寸）：

• 第一行放置 10x5 和 20x12 的矩形，宽度为 10+20=30，高度为 max(5,12)=12。
• 第二行放置 8x13 的矩形，宽度为 8，高度为 13。
• 最终窗口的尺寸为 30x25（宽度为第一行的宽度 30，高度为两行高度之和 12+13=25）。

输入

输入由一个或多个数据集组成，最后以仅包含值 0 的一行结束。每个数据集以包含一个整数 m 的一行开始，1 <= m <= 80，表示结果窗口的最大宽度。随后是至少一个且最多 15 行，每行包含一个矩形的尺寸，宽度在前，高度在后。矩形列表的结束由一对 -1 -1 标记，这不计入实际矩形的尺寸。每个矩形的宽度在 1 到 80 之间（包括 1 和 80），高度在 1 到 100 之间（包括 1 和 100）。

输出

对于每个输入数据集，打印结果窗口的宽度，后跟一个空格，然后是小写字母 "x"，再跟一个空格，最后是结果窗口的高度。

示例输入 1

35
10 5
20 12
8 13
-1 -1
25
10 5
20 13
3 12
-1 -1
15
5 17
5 17
5 17
7 9
7 20
2 10
-1 -1
0

示例输出 1

30 x 25
23 x 18
15 x 47

来源

Mid-Central USA 2004