Фейерверки в РайтЭнглесе
В городе RightAngleles улицы образуют бесконечную квадратную сетку, где любые две улицы либо параллельны, либо перпендикулярны друг другу, а расстояние между двумя соседними параллельными улицами одинаково (обозначим это расстояние как одна единица). Все улицы, ориентированные с запада на восток, называются горизонтальными и нумеруются последовательными целыми числами с юга на север. Улицы, ориентированные с юга на север, называются вертикальными и нумеруются последовательными целыми числами с запада на восток.
Каждый житель живет в доме, вход которого расположен на пересечении определенной горизонтальной и вертикальной улицы. В одном доме может проживать несколько жителей.
Мэр RightAngleles хочет повысить свою популярность, организовав фейерверк на пересечении главной горизонтальной улицы (с номером 0) и одной из вертикальных улиц. Известно, где живут жители, заинтересованные в том, чтобы прийти и насладиться фейерверком. Фейерверк будет виден вдоль обеих улиц, на пересечении которых он будет запущен; кроме того, по соображениям безопасности зрители должны находиться на расстоянии не менее S единиц от места запуска. Таким образом, если фейерверк будет запущен с пересечения с вертикальной улицей V, то каждый заинтересованный житель должен прийти на пересечение на главной горизонтальной улице (с номером 0) или вертикальной улице V, находясь не ближе, чем на S единиц от пересечения главной горизонтальной улицы и вертикальной улицы V. Например, если S=2, то наблюдение возможно с любого пересечения на главной горизонтальной улице, кроме тех, которые пересекаются с улицами V-1, V и V+1, и со всех пересечений на вертикальной улице V, кроме тех, которые пересекаются с горизонтальными улицами -1, 0 и 1.
Общий положительный эффект от фейерверка зависит от общей дистанции, которую жители должны преодолеть, чтобы наблюдать за запуском. Поэтому место для фейерверка должно быть выбрано так, чтобы минимизировать эту общую дистанцию.
Например, если S=2 и есть семь жителей, чьи местоположения показаны на карте (двое из них находятся в (-4;8)), то лучшее место для фейерверка — это пересечение главной улицы с 8-й вертикальной улицей; в этом случае общая дистанция, которую жители должны преодолеть, составляет 9 единиц.
Напишите программу, которая вычисляет минимально возможную общую дистанцию (в единицах), которую жители должны преодолеть, чтобы наблюдать за фейерверком.
Входные данные
Входные данные задаются в текстовом файле fire.in. Первая строка содержит два положительных целых числа, разделенных пробелами: количество жителей N (N ≤ 10^5) и безопасное расстояние S (S ≤ 10^6) в единицах. Следующие N строк содержат описания местоположений жителей. Каждая из этих строк содержит два целых числа H_i и V_i, разделенных пробелом; H_i и V_i (-10^9 ≤ H_i,V_i ≤ 10^9) обозначают номера горизонтальной и вертикальной улицы соответственно, на пересечении которых находится вход в дом i-го жителя.
Выходные данные
Первая и единственная строка текстового файла fire.out должна содержать ровно одно целое число — минимальную общую дистанцию (в единицах), которую жители должны преодолеть, чтобы наблюдать за фейерверком.