题目内容

在数据实验中，实验室准备了 $n$ 个样本。每个样本由三个整数 $(u_i, v_i, w_i)$ 描述，其中 $u_i$ 和 $v_i$ 均不为 $0$。对于任意两个样本，我们关心它们的“特征比值”。我们通过如下方式定义样本的特征类别：设 $g = \gcd(|u_i|, |v_i|)$，计算 $u_i' = u_i / g$，$v_i' = v_i / g$。如果 $u_i' < 0$，则取相反数 $(-u_i', -v_i')$，否则不变。最终得到的有序对 $(u_i', v_i')$ 称为该样本的 特征标识。若两个样本的特征标识相同，则称它们 同源；否则称为 异源。

研究员希望从中恰好选取 $k$ 个样本，并将选出的样本两两配对。当且仅当一对样本 异源 时，它们才能成功配对并产生一个有效数据点。同源的样本无法产生有效数据点。研究员的目标是最大化有效数据点的总数。请你计算，在最优选择下，最多能获得多少个有效数据点。

约束：

• $1 \le k \le n \le 10^5$
• $|u_i|, |v_i|, |w_i| \le 10^9$，且 $u_i eq 0$，$v_i eq 0$
• 任意两个样本的三元组 $(u_i, v_i, w_i)$ 互不相同

输入描述

第一行包含两个正整数 $n$ 和 $k$，分别表示样本总数和需要选择的样本数量。 此后 $n$ 行，每行包含三个整数 $u_i, v_i, w_i$，表示第 $i$ 个样本的三元组。

输出描述

输出一个整数，表示能够获得的最大有效数据点数量。

样例1

输入

3 1
1 2 10
2 4 20
-1 -2 30

输出

0

说明

所有样本归一化后的特征标识均为 $(1,2)$，全部同源。由于只需选择 $k=1$ 个样本，无法进行配对，有效数据点数为 0。

样例2

输入

2 2
3 4 0
6 8 1

输出

0

说明

两个样本归一化后均为 $(3,4)$，属于同源样本。即使将两个样本都选出来，它们之间也无法成功配对，因此最大有效数据点数为 0。

样例3

输入

4 3
1 1 1
2 2 2
1 2 3
2 1 4

输出

3

说明

各样本的特征标识计算如下：

• $(1,1,1)$：$\gcd(1,1)=1$，标识 $(1,1)$；
• $(2,2,2)$：$\gcd(2,2)=2$，标识 $(1,1)$；
• $(1,2,3)$：$\gcd(1,2)=1$，标识 $(1,2)$；
• $(2,1,4)$：$\gcd(2,1)=1$，标识 $(2,1)$。

与 $(1,1)$ 同源的样本有 2 个，其余两组各 1 个。要选出 $k=3$ 个样本，为了使有效数据点最大化，应当从三个不同组中各选 1 个样本，此时同源对数为 $0$，有效数据点达到 $\binom{3}{2}=3$。

样例4

输入

5 4
1 2 1
2 4 2
-1 -2 3
3 4 4
6 8 5

输出

4

说明

归一化后的特征标识：

• $(1,2,1)$、$(2,4,2)$、$(-1,-2,3)$ 的特征标识均为 $(1,2)$（第三组取反后得到 $(1,2)$），同源样本共 3 个；
• $(3,4,4)$、$(6,8,5)$ 的特征标识均为 $(3,4)$，同源样本共 2 个。

我们需要选出 $k=4$ 个样本。若选 3 个 $(1,2)$ 与 1 个 $(3,4)$，同源对数为 $\binom{3}{2}=3$；若每组各选 2 个，同源对数为 $\binom{2}{2}+\binom{2}{2}=2$。后者更优，此时总对数为 $\binom{4}{2}=6$，有效数据点为 $6-2=4$。