벌 떼

거센 폭풍이 벌 떼를 좌표평면 위에 흩어 놓았다. 지금 각 벌은 정수 좌표를 가진 어떤 점에 있다. 모든 벌은 정수 좌표를 가진 한 점에 함께 모이려고 한다. 이 벌 떼는 유전적 돌연변이가 있어서 정해진 방향으로만 날 수 있다. 허용된 방향은 동서남북 네 방위와 북동, 북서, 남동, 남서 네 방위를 합친 여덟 방향 중 일부이다. 북쪽은 $y$ 좌표가 커지는 방향이고 동쪽은 $x$ 좌표가 커지는 방향이다.

한 걸음에 벌 한 마리가 허용된 방향 중 하나로 이웃한 정수 좌표 점까지 이동할 수 있다. 예를 들어 북동쪽으로 한 걸음 가면 $(x, y)$에서 $(x+1, y+1)$로, 서쪽으로 한 걸음 가면 $(x, y)$에서 $(x-1, y)$로 이동한다. 모든 벌이 한 점에 모이는 데 필요한 걸음 수의 합의 최솟값을 구하라.

첫 번째 예제를 나타낸 그림

첫째 줄에 허용된 방향의 수 $d$가 주어진다. ($1 \le d \le 8$)

둘째 줄에 서로 다른 문자열 $d$개가 공백 하나씩을 사이에 두고 주어진다. 각 문자열은 N, NW, W, SW, S, SE, E, NE 중 하나이며, 차례대로 북, 북서, 서, 남서, 남, 남동, 동, 북동을 뜻한다.

다음 줄에 벌의 수 $n$이 주어진다. ($1 \le n \le 50$)

다음 $n$개의 줄 중 $k$번째 줄에 $k$번째 벌이 지금 있는 점의 좌표 $x_k$, $y_k$가 주어진다. ($-10^6 \le x_k, y_k \le 10^6$) 모든 벌은 서로 다른 점에 있다.

걸음 수의 합의 최솟값을 출력한다. 모든 벌이 한 점에 모일 수 있는 입력만 주어진다.