121 - Pipe Fitters

Background

Filters(一種程式,用於資料過濾並重新格式化輸出)是UNIX系統上的一個重要的程式類別,而管線(pipe)是作業系統裡的一個概念,能讓資料在行程(processe)間流通(並使多個filter能輕易地串在一起)。

本題討論如何使裝進容器內的管線(pipe)數量最大化,但這並非是一個裝箱問題 (bin packing problem),而是一個 pipe fitting problem。

The Problem

有一間工廠專門生產一種直徑固定的管線,所有的管線都被放在四方形的容器中儲存,而容器會有不同的大小。所有管線皆以列順序被儲存,所以每一列之間不會有多餘的空間(不過一列的最後可能會有多餘的空間),一列中的每個管線都是緊密地靠在一起。如下面四方形的橫截面圖,管線會有兩種置放的方式,一種是格子狀,如左邊的兩個圖;另一種是斜著擺,如右邊的兩個圖。

注意,雖然從圖中不一定能明顯地看出來,但是必須要強調的是相鄰兩列之間不會有多餘的空隙,任兩列(或與箱子的底部)都是緊密接觸的。當把箱子裝滿之後可能會有多餘的空間,但還不足以多放進一根管線,這樣的空間一般都會用東西填充,好讓在運輸途中的管線不會滾來滾去。

Input

輸入會給定一連串容器橫截面的長度與寬度,每一個橫截面的長寬會在一列的兩個數值中給定,並以空白字元隔開,長寬的單位大小等於管線的直徑。所有尺寸皆小於 $2^{7}$,注意 $ a \times b $ 與 $ b \times a $ 視為相同。

Output

針對每一組容器截面的尺寸,你的程式必須輸出該容器最多可以放進幾根管線,數量必須是整數。如果產生最大數量的排列方式是以格子狀排列,則在數量的後面加上 grid,若是以斜偏的方式排列則請輸出 skew,若任兩種排列方式都能放進最大數量的管線,則請優先輸出 grid。

Sample Input

3 3
2.9 10
2.9 10.5
11 11

Sample Output

9 grid
29 skew
30 skew
126 skew