Lunar Exploration

문제

때는 2035년, ANA 항공우주국은 달 탐사 프로젝트를 위해서 $N$개의 탐사 로봇을 달 표면 곳곳에 배치했다. 탐사 로봇들은 달의 토양과 암석을 성공적으로 채취했고, 이제 회수선을 통해 지구로 복귀해야 한다.

달 표면은 무한한 2차원 좌표 평면이라 생각할 수 있다. $x$ 좌표가 증가하는 방향이 동쪽, 감소하는 방향이 서쪽, $y$ 좌표가 증가하는 방향이 북쪽, 감소하는 방향이 남쪽이다.

각 탐사 로봇은 $1$부터 $N$까지 순서대로 번호가 매겨져 있고 $i(1≤i≤N)$번째 탐사 로봇은 정수 좌표 $(x_i, y_i)$에 배치되어 있다. 탐사 로봇이 놓여있지 않은 달 표면 어딘가에 회수선이 착륙했는데, 특이하게도 길이 $N$의 막대 모양이며 $x$-좌표축 또는 $y$-좌표축에 평행하다. 또한 회수선이 차지하는 각 정수 좌표마다 하나의 탐사 로봇을 보관할 수 있는 좌석이 하나씩, 총 $N$개가 설치되어 있다.

여러분은 단위 시간마다 하나의 탐사 로봇을 동서남북으로 1만큼 움직이도록 조종할 수 있다. 이때 모든 탐사 로봇이 회수선에 탑승하기 위해 걸리는 최소 시간을 구하는 프로그램을 작성해 보자. 단, 두 로봇이 충돌하면 폭발의 위험이 있기 때문에 이동 중에 두 로봇을 같은 좌표에 위치시키면 안 된다.

입력

첫째 줄에 탐사 로봇의 개수 $N$이 주어진다. $(1≤N≤100\,000)$

둘째 줄부터 N개의 줄에 각 탐사 로봇이 배치된 좌표 $x_i, y_i$가 공백으로 구분되어 주어진다. $(-1\,000\,000≤x_i,y_i≤1\,000\,000)$ 각 좌표는 모두 다르다.

마지막 줄에는 회수선이 위치한 시작 좌표 $X, Y$와 배치 방향 $D$가 공백으로 구분되어 주어진다. $(-1\,000\,000≤X,Y≤1\,000\,000; D\subset\{E, N\})$

• $D$가 E인 경우 회수선은 동쪽으로 배치되어 있고 $(X, Y), (X+1, Y), \cdots , (X+N-1, Y)$에 좌석이 설치되어 있음을 의미한다.
• $D$가 N인 경우 회수선은 북쪽으로 배치되어 있고 $(X, Y), (X, Y+1), \cdots , (X, Y+N-1)$에 좌석이 설치되어 있음을 의미한다.

회수선의 좌석이 설치된 좌표에는 탐사 로봇이 배치되어 있지 않다.

출력

모든 탐사 로봇이 회수선에 탑승하기 위해 걸리는 최소 시간을 출력한다.

예제 입력 1

5
2 3
-2 6
-1 1
4 0
3 -4
0 1 E

예제 출력 1

17