시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB422100.000%

문제

Одна из центральных площадей Архангельска замощена прямоугольными плитками размера $1 \times k$. Если ввести систему координат, так что левый нижний угол одной из плиток будет иметь координаты $(0, 0)$, то левые нижние углы плиток будут иметь координаты $(i \cdot k+j,j)$ для всех целых $i$ и $j$.

На площади было решено установить памятник известному архангельскому писателю и художнику Степану Писахову. Для установки памятника необходимо удалить все плитки, полностью или частично попадающие под его основание. Основание памятника имеет форму многоугольника с целочисленными координатами вершин, все стороны которого параллельны осям координат. Известно, что любая прямая, пересекающая основание памятника и параллельная одной из осей координат, в пересечении с основанием образует один отрезок.

Для установки памятника необходимо выбрать место на площади таким образом, чтобы количество удалённых плиток было минимальным. При выборе места основание разрешается только передвигать параллельно осям координат.

Требуется написать программу, вычисляющую минимальное количество плиток, которые придётся удалить.

입력

Первая строка входных данных содержит два числа $n$ и $k$ --- количество вершин в основании памятника и размер плитки.

Каждая из последующих $n$ строк содержит два целых числа $x_i$, $y_i$ --- координаты $i$-й вершины основания. Координаты перечислены в порядке обхода против часовой стрелки.

출력

Единственная строка выходных данных должна содержать минимально возможное количество плиток, которые необходимо удалить для размещения памятника на площади.

서브태스크

번호배점제한
132

$1 \le n \le 50$, $1 \le k \le 50$, $0 \le x_i, y_i \le 50$

237

$1 \le n \le 1000$, $1 \le k \le 1000$, $0 \le x_i, y_i \le 1000$

331

$1 \le n \le 100\,000$, $1 \le k \le 100\,000$, $0 \le x_i, y_i \le 1000\,000$

예제 입력 1

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

예제 출력 1

7

힌트

Исходное расположение основания памятника в первом примере.

Оптимальное расположение основания памятника в первом примере.

채점 및 기타 정보

  • 예제는 채점하지 않는다.