시간 제한메모리 제한제출정답맞힌 사람정답 비율
8 초 (추가 시간 없음) 1024 MB1227720.588%

문제

민준이는 얼마 전 COVID-19에 감염되었다. 이는 아주 고통스러운 과정이었기에, 민준이는 이제부터 사회적 거리두기 수칙을 철저히 지켜, 친구들과 적정 거리를 두고 감염의 여지를 아예 만들지 않고자 한다.

하지만 민준이는 친구들과 너무 거리를 두면, 친구들이 모두 떠나갈까봐 두렵다. 그래서, 민준이는 친구들과의 거리의 최솟값이 정확히 K가 되도록 하고 싶다. 다르게 말하자면, 친구들 중 가장 가까운 친구와의 거리가 더도 말고 덜도 말고 K가 되길 원한다는 것이다.

민준이에게는 N명의 친구가 있고, 친구 N명의 위치가 2차원 좌표평면 상에 주어진다. 현재 민준이가 원점에 있을 때, 민준이가 움직여야 할 최소 거리를 구하여라.

한 가지 주의할 점은, 민준이는 가로 혹은 세로 방향으로만 움직이기 때문에, 평면 상의 두 점 (x1, y1), (x2, y2)가 주어졌을 때, 거리는 |x1x2| + |y1y2|로 계산된다.

입력

첫째 줄에는 친구들의 수 N과 거리를 두고 싶은 정도 K가 주어진다. (1 ≤ N ≤ 106; 1 ≤ K ≤ 109)

둘째 줄부터 N개의 줄에 걸쳐 평면 상의 친구들의 위치 (xi, yi)가 두 정수로 주어진다. (|xi|, |yi| ≤ 109)

출력

첫째 줄에 친구들과의 거리의 최솟값이 K가 되도록 하기 위해서 필요한 이동거리의 최솟값을 출력한다.

예제 입력 1

4 3
2 1
-1 1
6 3
2 4

예제 출력 1

1

예제 입력 2

4 1
-4 3
2 2
1 5
2 -1

예제 출력 2

2