「游族杯」上海市高校程序设计邀请赛暨华东师范大学第九届 ECNU Coder 程序设计竞赛 (大一组)

I. 切西瓜

单点时限: 2.0 sec

内存限制: 256 MB

切西瓜的时候正好切到瓜子这种事情确实是有可能的,不过很少发生,因为瓜子实在太少了。

切西瓜的时候切到很多瓜子也是有可能的,只要西瓜里面的瓜子足够多。

现在有一把平的刀(你只能用一个平面把西瓜切成两半),刀的厚度可以忽略不计;有一个西瓜,已经通过某种手段获知,西瓜内部有 $n$ 个瓜子(瓜子可以看作一个点),每个瓜子用一个三维坐标表示。西瓜足够大,保证所有的瓜子都在西瓜内。问如果用刀去切西瓜,最多能切到多少瓜子。

输入格式

第 $1$ 行一个整数 $n$。

第 $2$ 到 $n+1$ 行,每行三个整数 $x_i,y_i,z_i$,表示第 $i$ 个瓜子的坐标是 $(x_i,y_i,z_i)$。数据保证每个坐标仅会出现一次。

数据包含 $10$ 个测试文件,每个测试文件含有单个测试点。其中:

  • 测试点 $1,2,3$ 满足:$3 \leq n \leq 4$。
  • 测试点 $4,5,6,7$ 满足:$3 \leq n \leq 80$。
  • 测试点 $8,9,10$ 满足:$3 \leq n \leq 200$。

对于所有测试点,满足 $-10^9 \leq x_i,y_i,z_i \leq 10^9$。

输出格式

输出一个整数,表示最多能切到多少瓜子。

样例

Input
3
0 0 0
1 0 1
0 1 1
Output
3
Input
4
0 0 0
1 0 1
0 1 1
1 1 1
Output
3

提示

三维空间平面方程为 $Ax+By+Cz+D=0$,其中 $A,B,C,D$ 为常数。