Космические исследования
시간 제한2초메모리 제한512 MB
k x k 크기 촬영 구역이 남서쪽 모서리에서 시작해 하루에 서쪽, 동쪽, 북쪽으로 1km씩만 움직일 수 있을 때, 주어진 모든 점을 촬영하는 최소 일수를 구한다.
문제
Отделу космических исследований поступило задание сфотографировать из космоса n объектов в заданной области. Область имеет форму квадрата размером 50×50 километров. Если разделить ее на квадраты размером 1×1 километр, то интересующие отдел объекты окажутся в центрах некоторых единичных квадратов.
Введем систему координат, направив ось OX с запада на восток и ось OY с юга на север. Тогда каждому единичному квадрату будут сопоставлены координаты в диапазоне от 1 до 50, как показано на рисунке ниже.
Для космической съемки используется специальный фотоаппарат высокого разрешения, установленный на космическом спутнике. Фотоаппарат может делать снимки квадратных участков земной поверхности размером k × k километров. Исходно аппарат наведен на юго-западный угол заданной области, то есть, если сделать снимок, на нем будут видны единичные квадраты с координатами x и yот 1 до k километров.
С помощью специальных двигателей можно изменять орбиту спутника, что приводит к изменению участка съемки. За один день орбиту спутника можно изменить таким образом, что участок съемки сместится либо на один километр на запад, либо на один километр на восток, либо на один километр на север. Переместить участок съемки на юг невозможно. Непосредственно между перемещениями спутника можно сделать снимок, временем съемки можно пренебречь.
Руководство отдела заинтересовалось вопросом: за какое минимальное количество дней можно сделать снимки всех объектов заданной области.
Требуется написать программу, которая по заданному расположению объектов и размеру снимка k определит минимальное время, за которое можно сделать снимки всех объектов заданной области.
입력
Первая строка входного файла содержит два целых числа: n и k (1 ≤ n ≤ 1000, 1 ≤ k ≤ 5).
Следующие n строк содержат по два целых числа: xi и yi — координаты объектов в заданной области (1 ≤ xi, yi ≤ 50).
출력
В выходном файле должно содержаться одно целое число: минимальное количество дней, которое требуется для получения снимков всех объектов в заданной области.
힌트
В первом примере возможна следующая последовательность действий: сделать снимок, 9 раз сместиться на восток, сместиться на север, сделать снимок, 9 раз сместиться на запад, сместиться на север, сделать снимок, 9 раз сместиться на восток, сместиться на север, сделать снимок. Всего требуется 30 перемещений участка съемки.
Во втором примере объекты расположены там же, но размер снимка больше, поэтому можно действовать так: сделать снимок, сместиться на север, сделать снимок, 8 раз сместиться на восток, сделать снимок, сместиться на север, сделать снимок. Всего требуется лишь 10 перемещений участка съемки.
В третьем примере перемещать участок съемки не требуется, можно просто сделать снимок.
Четвертый пример соответствует приведенному выше рисунку.