题目描述

过滤器，也就是以某种变化后的形式传递“已处理”数据的程序，是UNIX操作系统中一类重要的程序。管道是一种操作系统概念，它允许数据在进程之间“流动”（并且使得过滤器能够轻松地链接在一起）。

这个问题涉及到如何使能放入存储容器中的管道数量达到最大化（但这是一个管道放置问题，而不是装箱问题）。

有一家公司生产直径统一的管道。所有管道都存放在矩形的存储容器中，不过这些容器有多种不同的尺寸。在容器中，管道是按行存放的，这样每行中的管道之间没有空隙（一行的末尾可能会有一些空间），也就是说，一行中的所有管道都是相切的，即相互接触。在矩形横截面中，管道以网格模式或交错模式存放，如下所示：最左边的两个横截面是网格模式，最右边的两个横截面是交错模式。

请注意，尽管从图中可能不太明显，但任何一行中相邻的管道之间都没有空隙。任何一行中的管道都与下面一行的管道相切（接触）（或者放置在容器的底部）。当把管道装入容器时，可能会有“剩余”空间，无法再装入管道。这样的剩余空间会用填充物填充，以防止管道在运输过程中移动。

输入

输入是一系列存储容器横截面的尺寸。每个横截面由一行上的两个实数值表示，两个值之间用空白字符分隔。这些尺寸以管道直径为单位表示。所有尺寸都将小于$128$。请注意，尺寸为$a*b$的横截面也可以看作是尺寸为$b*a$的横截面。

输出

对于输入中的每个横截面，你的程序应该打印出能够装入该横截面的管道的最大数量。管道的数量是一个整数——不能装入部分管道。如果网格模式能装入最大数量的管道，在最大数量后面加上单词“grid”；如果交错模式能装入最大数量的管道，在最大数量后面加上单词“skew”。如果模式无关紧要，即使用网格模式或交错模式都能装入相同数量的管道，那么应该打印单词“grid”。

输入示例

3 3
2.9 10
2.9 10.5
11 11

输出示例

9 grid
29 skew
30 skew
126 skew

来源

1993年杜克大学互联网编程竞赛，UVA 121题