Swarm

A violent storm has scattered a swarm of bees across the coordinate plane. Each bee is now at some point with integer coordinates. All the bees want to gather at a single point, which must also have integer coordinates. The bees in this swarm share a genetic mutation, so they can fly only in certain directions. The allowed directions are a subset of the eight compass directions: the four cardinal directions and the four intercardinal directions (northeast, northwest, southeast, southwest). As usual, north is the direction of increasing $y$ and east is the direction of increasing $x$.

In one step, one bee can move to a neighboring integer point in one of the allowed directions. For example, one step northeast moves a bee from $(x, y)$ to $(x+1, y+1)$, and one step west moves it from $(x, y)$ to $(x-1, y)$. Find the minimum total number of steps needed for all the bees to end up at the same point.

Illustration of the first example

The first line contains an integer $d$ ($1 \le d \le 8$), the number of allowed directions.

The second line contains $d$ distinct strings separated by single spaces. Each string is one of N, NW, W, SW, S, SE, E, NE, which stand for north, northwest, west, southwest, south, southeast, east, and northeast, in that order.

The next line contains an integer $n$ ($1 \le n \le 50$), the number of bees.

The $k$-th of the following $n$ lines contains integers $x_k$ and $y_k$ ($-10^6 \le x_k, y_k \le 10^6$), the coordinates of the point where the $k$-th bee is now. All bees are at distinct points.

Print the minimum total number of steps. The input guarantees that all the bees can gather at one point.