UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2174. 元素之泉

统计 下载数据

Description

传说中的Dystopia大陆是一片神圣美丽的土地,上面生活着具有极高文明的种族Barbarian。这里是一个美好、人人平等、没有压迫的社会,就像世外桃源一般。 Dystopia大陆上有N处泉水,每种泉水含有M种元素:冰,火,木等等(固定比例)。每一处泉水都是无穷无尽的,但是每次对于每一个矿的开采都需要耗费大量的魔法。 这里的泉水是Dystopia大陆的灵性和精华之源,令许多周边种族朝思暮想,也因此常常招致来战争。由于Dystopia的人们不善于战争,为了保护这方乐土,Dystopia的人委托爱与美的化身Satan来帮助他们保卫国家。但是Satan不会无条件保护他们,每一次保护他都必须得到每种泉水各10100(10的100次方)升。 经过几次战争后,Dystopia的人们发觉Satan的要求实在太多了。为了减少魔法的使用,Dystopia的大法师决定尽可能减少开采的矿的数量,而是增加每个矿开采的泉水总量,然后通过一定比例调配以假乱真。比如有3处泉水,第一处是10%冰+10%火+80%木,第二处是20%冰+20%火+60%木,第三处是30%冰+30%火+40%木。我们可以只开采第一处和第三处的泉水,然后按照1:1的比例就可以调配出和第二处泉水完全相同的混合泉水。 现在大法师想知道有多少处泉水可以不开采,也就是有多少处泉水可以通过除它以外的其他泉水调配出来。如果有两处泉水的成分完全相同,大法师会不动脑子地认为它们都可以不开采,而不是必须开采一处或者都必须开采。

Input

输入的第一行包含两个整数N和M,如题所述。接下来N行,每行M个实数,分别是第i种元素的百分比。保证所有M个数之和为100。

Output

输出一个整数,表示可以不开采的泉水的数量。

Sample Input

【样例输入1】
3 3
10 10 80
20 20 60
30 30 40
【样例输入2】
2 1
100
100

Sample Output

【样例输出1】
1
【样例输出2】
2

Hint

5%数据满足:1≤N≤100,M=1。 15%数据满足:1≤N≤10000,M=2。 30%数据满足:M=3。 50%数据满足:M=4,且保证都是随机数据。 50%中有10%满足:M=4且1≤N≤10。所有数据满足:1≤NM(n的m次方)≤1012(10的12次方)。

Source