题目描述

一些地图制作者不满意地球不方便的球形，于是决定定制一颗平坦的多边形星球。所有坐标都位于笛卡尔平面中。

为了让星球上的每个人都能接入网络，他们会在多边形内部的每一个整点放置一台无线路由器。整点是横、纵坐标均为整数的点。题目保证多边形边界上没有整点。

多边形各顶点的坐标都是具有相同分母 $d$ 的分数。按边界顺序给出 $n$ 个点 $(x_i,y_i)$ 后，第 $i$ 个顶点的实际坐标为

请计算需要放置多少台路由器，即严格位于多边形内部的整点数量。

输入格式

第一行包含两个整数 $n,d$，分别表示顶点数和所有坐标的公共分母。

接下来 $n$ 行，每行包含两个整数 $x_i,y_i$。这些顶点按多边形边界顺序给出，顺时针或逆时针均可。

输出格式

输出一个整数，表示严格位于多边形内部的整点数量。

样例 1

4 2
1 1
7 1
3 3
3 5

2

样例 2

4 100
20 100
99 100
295 301
1 301

3

样例 3

4 100
100 20
100 99
301 295
301 1

3

样例 4

3 10
1234 2345
3000 1357
2345 2999

11262

数据范围与保证

• $3\le n\le50$；
• $2\le d\le10^9$；
• $1\le x_i,y_i\le10^9$；
• 任意两个顶点互不相同；
• 除相邻边在公共端点处相交外，任意两条边（包括端点）均不相交，因此给出的图形是简单多边形；
• 多边形边界上没有整点；
• 答案保证能用 64 位有符号整数表示。