#P18819. [Croatian CPC2016] Roj

[Croatian CPC2016] Roj

[Croatian CPC2016] Roj

题目描述

暴风雨将一群蜜蜂吹散到了平面上的不同整数坐标点。它们希望在某一个整数坐标点会合。

所有蜜蜂只能沿同一组允许的方向移动。允许方向是八个方向 N、NW、W、SW、S、SE、E、NE 的一个非空子集,分别代表北、西北、西、西南、南、东南、东、东北。北方为 yy 坐标增大的方向,东方为 xx 坐标增大的方向。

每一步,一只蜜蜂可以沿某个允许方向移动到相邻的整数坐标点。例如,N 表示坐标增加 (0,1)(0,1),SE 表示增加 (1,−1)(1,-1)。

你可以任意选择会合点。求所有蜜蜂到达同一个会合点所需的总步数的最小值。

第一个样例的示意图

输入格式

第一行包含一个整数 dd(1≤d≤81\le d\le8),表示允许的方向数。

第二行包含 dd 个互不相同的方向字符串,用空格分隔。每个字符串均为上文列出的八种之一。

第三行包含一个整数 nn(1≤n≤501\le n\le50),表示蜜蜂的数量。

接下来 nn 行,第 kk 行包含两个整数 xk,ykx_k,y_k(−106≤xk,yk≤106-10^6\le x_k,y_k\le10^6),表示第 kk 只蜜蜂的初始位置。

保证所有初始位置互不相同,且一定存在所有蜜蜂都能到达的整数坐标会合点。

输出格式

输出一个整数,表示所需总步数的最小值。

样例 1

输入

3
N NE NW
5
1 1
5 1
1 4
3 3
2 3

输出

13

样例 2

输入

3
N SE SW
3
-4 1
-4 -2
4 -2

输出

16

样例 3

输入

6
N E W SW NE NW
3
249 218
443 -290
231 -444

输出

1013

样例 4

输入

3
S SE NE
4
437 -368
387 -47
-422 136
-407 -300

输出

2025