問題文

魔法使いのコアさんは、$1,2,\dots,N$ の番号が付いた $N$ 個の魔道具を作りました。

各魔道具には性能を表す $K$ 個の値が設定されており、魔道具 $i$ $(1 \leq i \leq N)$ の $j$ $(1 \leq j \leq K)$ 番目の値は $S_{i,j}$ です。

コアさんは、これらの魔道具の保管にかかる費用をなるべく小さく抑えたいので、
次の条件を満たす魔道具 $x$ $(1 \leq x \leq N)$ をすべて売却することにしました。

• $\boldsymbol{x}$ と異なるある整数 $y$ $(1 \leq y \leq N)$ が存在し、任意の整数 $k$ $(1 \leq k \leq K)$ に対して $S_{x,k} \leq S_{y,k}$ が成り立つ。

このとき、コアさんが売却する魔道具の個数を求めてください。

制約

• $1 \leq N \leq \min(2 \times 10^{5}, 5^{K})$

• $1 \leq K \leq 8$

• $0 \leq S_{i,j} \leq 4$ $(1 \leq i \leq N \text{ かつ } 1 \leq j \leq K)$

• $( S_{i,1}, S_{i,2}, \dots, S_{i,K} ) \neq ( S_{j,1}, S_{j,2}, \dots, S_{j,K} )$ $(1 \leq i < j \leq N)$

• $N, K$ 及び $S_{i,j}$ $(1 \leq i \leq N \text{ かつ } 1 \leq j \leq K)$ はすべて整数

入力

入力は次の形式で与えられます。

$N$ $K$
$S_{1,1} S_{1,2} \cdots S_{1,K}$
$S_{2,1} S_{2,2} \cdots S_{2,K}$
 $\vdots$    $\ddots$    $\vdots$
$S_{N,1} S_{N,2} \cdots S_{N,K}$

• $1$ 行目には $N, K$ がこの順に半角スペース区切りで与えられる

• $(1 + i)$ $(1 \leq i \leq N)$ 行目には $S_{i,1}, S_{i,2} \dots, S_{i,K}$ がこの順に長さ $K$ の文字列として与えられる

出力

答えを $1$ 行に出力してください。

サンプル

3 3
210
420
004

1

2 2
40
04

0

5 1
2
3
0
1
4

4

1 8
44444444

0