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)$

$N+2$번째 줄에 회수선이 위치한 시작 좌표 $X,Y$와 배치 방향 $D$가 공백으로 구분되어 주어진다. (-1\\, 000\\, 000≤X,Y≤1\\, 000\\, 000;D\in\\{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)$에 좌석이 설치되어 있음을 의미한다.

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

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