Problem7414--Free Candies

7414: Free Candies

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

有 4 根竖直的管子,每个管子里有 n 颗糖果叠成一堆。
有一个篮子,最多可以放 5 颗糖果。
每次可以取走任意一个管子的最上方的一颗糖果放到篮子里,若篮子里有两颗糖的颜色相同,可以将这一对糖果放进口袋。
求最多可以放多少对糖果到口袋里。

Input

输入有若干组(不超过10组)测试数据,
对于每组测试数据: 
第一行一个整数 n (1≤n≤40),表示每根管子有多少糖果,
接下来 n 行,每行 4 个整数,第 i 行第 j 列表示第 j 根管子的第 i 颗糖果的颜色。糖果的颜色不超过 20 种,分别编号为 1 到 n。
输入最后一行,用一个 0 表示结束。

Output

输出共若干行,对每组测试数据依次输出答案,各占一行。

Sample 1 Input

5
1 2 3 4
1 5 6 7
2 3 3 3
4 9 8 6
8 7 2 1
1
1 2 3 4
3
1 2 3 4
5 6 7 8
1 2 3 4
0

Sample 1 Output

8
0
3

HINT

相同题目:UVa 10118

Source/Category

记忆化搜索