일몰

당신은 더운 나라를 방문하고 있으며, 마침 몹시 뜨거운 날이지만 다행히 한 집의 그늘에 있다. 언젠가는 호텔로 이동해야 한다는 것을 깨달았지만, 동시에 햇볕 아래로 나가기에는 너무 덥다는 것도 깨달았다. 당신이 있는 도시는 격자 위에 배치된 $N$채의 집으로 이루어져 있으며, 각 집은 정확히 1칸을 차지한다. 현재 모든 집에는 길이가 정확히 1칸이고 북쪽을 향하는 그늘이 있으며, 해가 지기 시작했으므로 이 그늘의 길이는 시간 단위마다 1칸씩 늘어난다. 두 그늘이 길이가 적어도 1인 변을 공유하면 한 집의 그늘에서 다른 집의 그늘로 이동할 수 있다(그림 참조). 집을 통과해서 걸을 수는 없다. 이제 문제는 화상을 입지 않는 호텔까지의 경로가 생기려면 얼마나 오래 걸리는지를 구하는 것이다. 호텔은 $N$번 집이고, 당신은 1번 집의 그늘에 있다. 호텔 입구는 집의 북쪽에 있으므로 그쪽까지 이동해야 한다. 최악의 경우에는 $K$시간 단위 뒤에 찾아오는 밤까지 기다려야 할 수도 있다.

채점

당신의 풀이는 여러 테스트 케이스 그룹으로 평가된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 해결해야 한다.

모든 테스트 그룹에 $1 \le N, 0 \le K$이 적용된다.

그룹  |  배점  |  제한

1  |  19  |  $N, K \le 100, 0 \le x, y \le 100$

2  |  26  |  $N, K \le 1000, 0 \le x, y \le 1000$

3  |  17  |  $N, K \le 1000, 0 \le x, y \le 100000$

4  |  23  |  $N \le 20000, K \le 10^7, 0 \le x, y \le 10^7$

5  |  15  |  $N \le 300000, K \le 10^{18}, 0 \le x, y \le 10^{18}$

첫 번째 줄에는 도시의 집 수와 밤이 되기까지 남은 시간 단위 수를 나타내는 두 정수 $N$과 $K$이 주어진다. 이어지는 $N$개의 줄에는 각 집의 좌표 $x y$를 나타내는 정수 2개가 한 줄에 주어진다. 첫 번째 줄에는 당신이 그늘에 서 있는 집의 좌표가 주어지고, 마지막 줄에는 호텔의 좌표가 주어진다.

각 집에는 그늘이 있음이 보장된다. 즉, 어떤 집도 다른 집 바로 남쪽 칸에 있지 않다.

그늘만을 통과하는 호텔까지의 완전한 경로가 생길 때까지 걸리는 시간을 나타내는 정수를 출력한다. 걸리는 시간이 $K$ 이상이면 "NATT"을 출력한다.