题目描述

给定一个凸多边形和整数 $N$。横、纵坐标均为整数的点称为整点。位于多边形内部或边界上的点，都视为被多边形覆盖。

如果一条线段上至少包含 $N$ 个被多边形覆盖的整点，则称它为一条 $N$-酷线段。线段的端点也计入线段所包含的点。

如果一个点是被多边形覆盖的整点，并且是某条 $N$-酷线段的端点，则称它为一个 $N$-酷点。

请计算这个凸多边形覆盖的 $N$-酷点数量，每个点只计数一次。

多边形由若干坐标点给出，输入顺序任意，可能出现重复点，也可能有多个给定点位于同一条边上。这些点的凸包就是所给多边形，保证其面积非零。

输入格式

第一行包含两个整数 $M,N$，分别表示给定坐标点的数量和定义酷线段所需的整点数量。

接下来 $M$ 行，每行包含两个整数 $x_i,y_i$，表示一个给定点的坐标。

输出格式

输出一个整数，表示多边形覆盖的 $N$-酷点数量。

样例 1

5 6
0 3
1 1
2 6
7 1
7 5

21

样例 2

3 2
0 0
1 0
0 1

3

样例 3

9 3
0 0
0 1
1 2
2 2
2 1
1 0
0 0
0 0
2 2

6

数据范围与保证

• $3\le M\le50$；
• $2\le N\le500000$；
• $0\le x_i,y_i\le10000$；
• 多边形是面积非零的凸多边形；
• 多边形内部及边界上的整点总数不超过 $500000$。

样例说明

样例 2 中，三角形的三条边均包含两个整点，因此三个顶点都是 $2$-酷点。

样例 3 说明输入中可能多次给出同一个点，重复输入不影响所求的整点数量。