← 返回题目列表

Codeforces · 183/B

B. 动物园

中文机器翻译题面 查看原题

网格王国中的动物园由无限网格表示。动物园有 n 个观测双筒望远镜位于 OX 轴上。对于 1 和 n(含)之间的每个 i,都存在位于坐标为 (i, 0) 的点处的单个双筒望远镜。动物园里有 m 只火烈鸟,位于坐标为正的点上。火烈鸟目前正在睡觉,你可以假设它们一动不动。

为了获得火烈鸟的良好视野,每个双筒望远镜都可以独立旋转以面向任何角度(不一定是整数)。然后,可以使用双筒望远镜观察位于以设定角度穿过双筒望远镜的直线上的所有火烈鸟。换句话说,您可以为每个双筒望远镜分配一个与穿过双筒望远镜的任何直线相对应的方向,双筒望远镜将能够看到位于该直线上的所有火烈鸟。

今天,来自著名的 Codeforces 幼儿园的一些孩子去动物园进行了实地考察。他们的老师希望为每个双筒望远镜设置一个角度,以最大限度地增加双筒望远镜可以看到的火烈鸟的数量。老师对所有双筒望远镜的这些值的总和非常感兴趣。请帮他找到这笔钱。

输入

第一行包含两个空格分隔的整数 n 和 m (1 ≤ n ≤ 106, 1 ≤ m ≤ 250),分别表示双筒望远镜的数量和火烈鸟的数量。

接下来是 m 行,第 i 行将包含两个空格分隔的整数 xi 和 yi (1 ≤ xi, yi ≤ 109),这意味着第 i 个火烈鸟位于点 (xi, yi)。

所有火烈鸟都将位于不同的点。

输出

打印一个整数,表示所有双筒望远镜可以看到的火烈鸟的最大总数。

示例

输入 #1

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

输出 #1

11

注意

此图显示了示例测试用例的答案。