题目背景

译自 ROI 2015 Day1 T2. Памятник

题目描述

阿尔汉格尔斯克市中心的一处广场铺设着大小为 $1 \times k$ 的长方形地砖。若建立一个坐标系，使其中一块地砖的左下角位于坐标点 $(0, 0)$，则所有地砖的左下角坐标可表示为 $(i \cdot k + j,\, j)$，其中 $i$ 和 $j$ 为任意整数。

:::align{center} :::

现在在广场上计划建立一座纪念碑，以纪念著名的阿尔汉格尔斯克作家兼画家斯捷潘·皮萨霍夫。为了安装纪念碑，需要移除所有完全或部分位于其基座下方的地砖。

纪念碑的基座是一个顶点坐标为整数的多边形，其所有边都平行于坐标轴。已知任意一条平行于坐标轴的直线与该多边形相交时，最多只会形成一个连续的线段。

在选择纪念碑的放置位置时，只允许平移该多边形（即沿平行于坐标轴的方向移动），而不能旋转或缩放。目标是找到一种放置方式，使得需要移除的地砖数量最少。

请编写一个程序，计算安装纪念碑时最少需要移除的地砖数量。

输入格式

第一行包含两个整数 $n$ 和 $k$，分别表示纪念碑基座的顶点数以及每块地砖的边长。

接下来的 $n$ 行中，每行包含两个整数 $x_i$ 和 $y_i$，表示基座第 $i$ 个顶点的坐标。顶点按照逆时针顺序给出。

输出格式

输出一个整数——纪念碑可以放置的情况下，需要移除的地砖的最小数量。

12 3
2 3
1 3
1 2
3 2
3 1
8 1
8 2
10 2
10 3
8 3
8 4
2 4

7

8 4
1 0
5 0
5 2
4 2
4 3
2 3
2 1
1 1

5

提示

样例解释

下图展示了第一个样例中纪念碑基座的初始位置。

:::align{center} :::

随后展示了第一个样例中纪念碑基座的最优放置位置，此时需要移除的地砖数量最少。

:::align{center} :::

数据范围

子任务编号	分值	$n$	$k$	$x_i, y_i$ 的范围
1	32	$1 \le n \le 50$	$1 \le k \le 50$	$0 \le x_i, y_i \le 50$
2	37	$1 \le n \le 1000$	$1 \le k \le 1000$	$0 \le x_i, y_i \le 1000$
3	31	$1 \le n \le 100\,000$	$1 \le k \le 100\,000$	$0 \le x_i, y_i \le 1\,000\,000$