解题思路

设选出的 $k$ 条红色直线中，一共有 $x_1,x_2,\dots,x_m$ 条分别来自若干个平行线组，其中：

• 同一组内任意两条直线互相平行，不会产生“红点”
• 不同组之间任意两条直线一定相交，且恰好产生一个“红点”

于是，若总共选了 $k$ 条直线，那么本来一共有 $\binom{k}{2}$ 对直线。 其中，只有同组内的两条直线不会相交，所以答案就是：

题目内容

小红有 $n$ 条直线。她准备把其中的 $k$ 条直线染成红色。

任意两条染成红色的直线若相交，那么就称它们相交产生了一个“红点”。小红希望你能帮助她在 $n$ 条直线中恰选 $k$ 条进行染色，使得最终“红点”的数量尽可能多。

“红点”的定义与产生红点的两条直线绑定，不与所在的坐标绑定。例如，若红色直线 $A、B、C$ 都相交于同一个点，那么直线 $A,B、A,C$ 和 $B,C$ 各自产生一个“红点”，三条直线一共产生 $3$ 个“红点”。

输入描述

第一行输入两个正整数 $n,k(1≤n≤10^5;1≤k≤n)$ 代表直线的数量、小红需要染红的直线数量。此后 $n$ 行，第 $i$ 行输入三个整数 $a_i,b_i,c_i(-10^9≤a_i,b_i,c_i≤10^9)$ 代表第 $i$ 条直线的解析式为 $a_i×x+b_i×y+c_i=0$ 。保证 $a_i$ 和 $b_i$ 均不为零，且没有两条直线是重合的。

输出描述

输出一个整数，代表小红能得到的“红点”数量的最大值。

样例1

输入

3 2
1 1 1
1 1 2
1 2 1

输出

1

说明

选择前两条线染为红色不能得到“红点”，而无论选择第一条与第三条的组合还是第二条与第三条的组合都只能得到一个“红点”。所以，小红最多只能得到 $1$ 个“红点”。