TopCoder

會寫程式的羊
咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩

User's AC Ratio

100.0% (16/16)

Submission's AC Ratio

62.5% (20/32)

Tags

Description

源 達博在一次的旅途中,在月亮山中迷了路,同時又因為他的提款卡鎖在櫃子裡,沒有帶出來,由於飢餓難耐,源 達博最後不支倒地。這時候路過的赤円円將他帶到円円族的部落,供吃供住,並且帶他離開月亮山。事後源 達博為了答謝円円們的幫助,準備了很多禮物要送給「他們的」。

源 達博現在已經準備好六種大小不同的禮物,其面積大小分別有:$1\times 1$ , $2\times 2$ , $3\times 3$ , $4\times 4$ , $5\times 5$ , $6\times 6$等六種尺寸,這些禮物高度皆為 $h$。而他的女秘書幫他準備好了面積為$6\times 6$的箱子,高度 $h$ 的正方形箱子用來放禮物。

物品中$N\times N$的那兩面都會印上商標,而側面則不會。源 達博為了表達他的誠意,他要求物品一定都要直放(如上圖),這樣子才能夠不管之後怎麼拿取都能看到商標。所以可以將物品及箱子視為在一個二維平面上。

由於成本關係,源 達博希望所有的禮物放在最少的箱子裡寄出。請你寫一個程式計算出贈送這些禮物最少需要多少個箱子,這可以替源 達博省下不少錢,讓他以後可以多包一點紅包。

Input Format

輸入的第一行包含一個正整數 $T (T \leq 2400)$,代表測試資料的個數。每個測試資料一列(就是一次送禮),含有 $6$ 個整數(數字的範圍不超過$32767$)。分別代表 $1\times 1$ 到 $6\times 6$ 產品的數目。

Output Format

對每一組測試資料,輸出贈送這些禮物最少需要多少個箱子。

Sample Input 1

8
0 0 4 0 0 1
7 5 1 0 0 0
0 0 0 0 0 3
79 96 94 30 18 14
53 17 12 98 76 54
83 44 47 42 80 3
15 26 13 29 42 40
41 61 36 90 54 66

Sample Output 1

2
1
3
86
231
137
115
219

Hints

範例輸入第一筆測試資料使用最少箱子的擺法,使用 $2$ 個箱子。

範例輸入第二筆測試資料使用最少箱子的擺法,使用 $1$ 個箱子。。

Problem Source

NEOJ Problem 78

Subtasks

No. Testdata Range Constraints Score
1 0~9 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 131072 65536 1
1 1000 131072 65536 1
2 1000 131072 65536 1
3 1000 131072 65536 1
4 1000 131072 65536 1
5 1000 131072 65536 1
6 1000 131072 65536 1
7 1000 131072 65536 1
8 1000 131072 65536 1
9 1000 131072 65536 1