Problem4522--Giftbox

4522: Giftbox

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Status] [Submit] [Creator:]

Description

小科和小丁是好朋友,小丁的生日快到了,因此,小科正考虑准备一份意外的礼物。通常参加生日聚会时,过生日的人都会当场打开生日礼物,然后表示感谢。 小科知道小丁在收到重要的东西时,会很急于知道东西是什么,因此他想开一个玩笑^_^

小科进入礼品店,里面有很多不同种类的礼品盒,他打算一个礼品盒用来包装礼物,然后将其放入另一个更大的盒子中,然后再将这个更大的盒子放入另一个更大的盒子中...以此类推。因此,小丁只有在打开最里面的礼物盒之后,才能看到礼物。可以想象一下他打开盒子的过程,会是多么的急迫^_^

礼品盒是n维的。一个维数为n的礼物盒(X1,x2,……,Xn)可以放在另一个n维(Y1,Y2,Y3,……,Yn)盒子中,只要满足如下条件:

存在一个序列π,使得: Xπ1 < Y1, Xπ2 < Y2, …, Xπn < Yn都成立。

如果它满足上述标准,就可以放进盒子里,小科希望选择尽可能多的盒子来装礼物。

Input

输入文件包含多个测试用例。 

每个测试用例:

第一行:包含两个数字:第一个是正整数N(1<=N<=500),即礼品店中的盒子数;第二个是正数d(3<=d<=1000),即所有盒子的维数。

下一行:包含代表礼物尺寸的d个正整数(G1,G2,…,Gd),表示礼物的维数信息。 

随后N行:每行包含d个正整数(X1,X2,…,Xd),表示每个礼物盒的维数信息。

遇到的所有数字都是正整数且小于2^31,以文件末结尾。

Output

每个测试用例的输出将只包含一行

输出小科可以选择的礼物盒的最大数量

如果Bobobo找不到任何可以装礼物的盒子,输出: Please look for another gift shop! 

Sample Input Copy

5 7
4 6 8 2 7 5 3
2 8 13 6 10 9 4
80 70 12 3 6 8 2
8 7 4 6 9 10 12
100 200 300 400 500 600 700
800 800 800 800 800 800 800

Sample Output Copy

3

Source/Category

K12440