C0945 [SDOI2013]spring

内存限制:256 MB 时间限制:4000 ms

题目描述

作为光荣的济南泉历史研究小组中的一员,铭铭收集了历史上 $x$ 个不同年份时不同泉区的水流指数,这个指数是一个小于 $2^{30}$ 的非负整数。第 $i$ 个年份时六个泉区的泉水流量指数分别为 $A(i,1)$,$A(i,2)$,$A(i,3)$,$A(i,4)$,$A(i,5)$ 与 $A(i,6)$。

现在铭铭希望知道有多少对不同的年份:$i$ 和 $j$,满足这两年恰好有 $K$ 个泉区的泉水流 $S$ 指数对应相同。

输入格式

第一行有 $2$ 个整数,分别是 $N$ 和 $K$

之后 $N$ 行,每行有 $6$ 个整数。第 $i$ 行的第 $j$ 个数字 $A(i,j)$ 表示第 $i$ 个年份中第 $j$ 个泉区的泉水流量指数。

输出

一个整数表示有多少对不同的年份满足恰有 $K$ 个区的泉水流量指数对应相同。

样例

样例输入 1

3 3 1 2 3 4 5 6 1 2 3 0 0 0 0 0 0 4 5 6

样例输出 1

2

提示

对于 $100\%$ 的数据,$0 \le K \le 6$,且所有数据中 $K$ 是等概率出现的,即对于任意的 $0 \le x$ 都有大约 $1/7$ 的数据中 $K=x$, $N \le 100000$。