Задача D. Космические исследования ≡

Условие

Отделу космических исследований поступило задание сфотографировать из космоса n объектов в заданной области. Область имеет форму квадрата размером 50 × 50 километров. Если разделить ее на квадраты размером 1 × 1 километр, то интересующие отдел объекты окажутся в центрах некоторых единичных квадратов.

Введем систему координат, направив ось OX с запада на восток и ось OY с юга на север. Тогда каждому единичному квадрату будут сопоставлены координаты в диапазоне от 1 до 50, как показано на рисунке ниже.

Для космической съемки используется специальный фотоаппарат высокого разрешения, установленный на космическом спутнике. Фотоаппарат может делать снимки квадратных участков земной поверхности размером K × K километров. Исходно аппарат наведен на юго-западный угол заданной области, то есть, если сделать снимок, на нем будут видны единичные квадраты с координатами X и Y от 1 до K километров.

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

Руководство отдела заинтересовалось вопросом: за какое минимальное количество дней можно сделать снимки всех объектов заданной области.

Требуется написать программу, которая по заданному расположению объектов и размеру снимка K определит минимальное время, за которое можно сделать снимки всех объектов заданной области.

Пояснения к примерам

В первом примере возможна следующая последовательность действий: сделать снимок, 9 раз сместиться на восток, сместиться на север, сделать снимок, 9 раз сместиться на запад, сместиться на север, сделать снимок, 9 раз сместиться на восток, сместиться на север, сделать снимок. Всего требуется 30 перемещений участка съемки.

Во втором примере объекты расположены там же, но размер снимка больше, поэтому можно действовать так: сделать снимок, сместиться на север, сделать снимок, 8 раз сместиться на восток, сделать снимок, сместиться на север, сделать снимок. Всего требуется лишь 10 перемещений участка съемки.

В третьем примере перемещать участок съемки не требуется, можно просто сделать снимок.

Четвертый пример соответствует приведенному выше рисунку.

Система оценивания

Решения, правильно работающие только для K = 1, будут оцениваться из 30 баллов.

Решения, правильно работающие только для K > 1 и 1 < N ≤ 15, будут оцениваться из 30 баллов.

Формат входного файла

Первая строка входного файла содержит два целых числа: N и K

Следующие N строк содержат по два целых числа: X_i и Y_i — координаты объектов в заданной области.

Формат выходного файла

В выходном файле должно содержаться одно целое число: минимальное количество дней,которое требуется для получения снимков всех объектов в заданной области.

Ограничения

1 ≤ N ≤ 10³

1 ≤ K ≤ 5

1 ≤ X_i, Y_i ≤ 50

Примеры тестов

4 1
1 1
10 2
1 3
10 4

30

4 2
1 1
10 2
1 3
10 4

10

1 1
1 1

0

3 3
3 3
3 6
6 3

7