题目背景

约翰乘坐一班长途航班前往拉斯维加斯，准备参加 TopCoder 总决赛。航程要持续好几个小时，他一时睡不着，便打开了自己最喜欢的手机激光游戏消磨时间。

游戏地图是一块由整点构成的正方形区域。地图左下角安装着一门激光炮，其余整点上原本各有一只怪物。不过，有些怪物听说约翰即将上线，提前逃离了战场。约翰的激光炮只能发射有限次数，因此他想安排好每一发激光的方向，尽可能消灭更多怪物。

题目描述

给定一个 $n\times n$ 的二维整点区域，行号和列号均为 $0,1,\ldots,n-1$。

• 行号从下到上递增；
• 列号从左到右递增；
• 激光炮位于 $(0,0)$；
• 除 $(0,0)$ 外，每个整点最初都有一只怪物；
• 给定的若干整点上的怪物已经逃走。

约翰最多可以发射 $k$ 次激光。每次发射时，他可以选择任意方向，从 $(0,0)$ 发出一条无限长的射线。射线会消灭其路径上的所有现存怪物。

怪物可以视为没有大小的点。若多个怪物与原点位于同一条射线上，一次射击可以同时消灭它们。

请计算约翰使用不超过 $k$ 次射击最多能够消灭多少只怪物。

输入格式

第一行输入三个整数 $n,k,m$，分别表示地图边长、最多射击次数以及已经逃走的怪物数量。

接下来 $m$ 行，每行输入两个整数 $r_i,c_i$，表示坐标 $(r_i,c_i)$ 处的怪物已经逃走。

输出格式

输出一个整数，表示最多能够消灭的怪物数量。

样例 1

输入

3 4 3
1 1
0 1
1 0

输出

4

说明

所有仍在战场上的怪物分别位于不同的有效射线上，因此每一发激光至多消灭一只怪物。约翰最多发射 $4$ 次，所以答案为 $4$。

样例 2

输入

2 1000000000 3
1 1
0 1
1 0

输出

0

说明

除激光炮所在位置外的三只怪物都已经逃走，因此无论发射多少次激光，都无法消灭怪物。

样例 3

输入

9 1 7
8 2
0 1
7 6
6 8
3 3
0 5
3 4

输出

8

说明

约翰只能发射一发激光。选择一条没有怪物逃走且包含 $8$ 个整点的方向即可消灭 $8$ 只怪物。

样例 4

输入

6 9 5
0 3
2 4
3 3
4 2
2 0

输出

18

样例 5

输入

8 9 7
3 6
5 0
4 5
6 2
0 2
0 6
2 5

输出

30

数据范围

• $2\le n\le 4\,000\,000$；
• $1\le k\le 16\,000\,000\,000\,000$；
• $1\le m\le \min(n^2-1,625)$；
• $0\le r_i,c_i<n$；
• 所有逃走怪物的坐标互不相同；
• 不会给出坐标 $(0,0)$。

所有答案均可用有符号 $64$ 位整数表示。