I. Neptune
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Recently, Poseidon has gotten addicted to a game called Craftmine. In Craftmine, there is a crafter that consists of $$$k$$$ slots, each of which can store an unlimited amount of a single type of ingredient. If the slot has 0 ingredients, it is considered empty. A recipe represents a configuration of the crafter that will produce a desired product. Each recipe is an array of length $$$k$$$ whose elements are either an empty slot or a type of ingredient.

Each time the crafter is used, it checks if the current configuration matches a recipe by comparing the ingredients in each of the slots (but not the amount of each ingredient). If the configuration matches a recipe, every slot uses up exactly 1 of the ingredients in that slot (except for empty slots, where nothing happens).

Currently, Poseidon has $$$n$$$ unique recipes and (being a god) has an unlimited amount of all ingredients. However, Poseidon is quite lazy, so he plans to fill the crafter only once, then use it as many times as he can to create unique recipes.

What is the maximum number of unique recipes that can be created after filling the crafter once?

Warning: Java and Python solutions are probably too slow for this problem.

Input

The first line of input contains $$$n$$$ and $$$k$$$ $$$(1\leq n\leq 2000, 1\leq k\leq 2000)$$$.

The $$$i$$$th of the next $$$n$$$ lines contains recipe $$$i$$$, which is an array $$$a_i$$$ of $$$k$$$ integers, with 0 representing an empty slot, and all other numbers representing a type of ingredient $$$(0\leq a_{i,j} \leq 100)$$$.

Output

Output a single integer, the maximum number of unique recipes that can be created after filling the crafter exactly once.

Example
Input
5 4
0 0 1 0
2 0 1 0
3 0 1 0
3 10 1 0
2 2 1 0
Output
3
Note

Poseidon can put 2 of item 3 in the 1st slot, 1 of item 10 in the 2nd slot, 3 of item 1 in the 3rd slot, and nothing in the 4th slot: $$$\{3_2, 10_1, 1_3, \emptyset\}$$$.

Using the crafter now will yield recipe 4 ($$$\{3,10,1,\emptyset\}$$$). After the ingredients are used up for the recipe, the crafter becomes $$$\{3_1,\emptyset, 1_2, \emptyset\}$$$.

Using the crafter now will yield recipe 3 ($$$\{3,\emptyset, 1, \emptyset\}$$$). After the ingredients are used up for the recipe, the crafter becomes $$$\{\emptyset, \emptyset, 1_1, \emptyset\}$$$.

Using the crafter now will yield recipe 1 ($$$\{\emptyset, \emptyset, 1, \emptyset\}$$$). After the ingredients are used for the recipe, the crafter becomes $$$\{\emptyset, \emptyset, \emptyset, \emptyset\}$$$).

At this point, no more recipes can be made. Since 3 unique recipes were made, the answer is 3.