#P18819. [Croatian CPC2016] Roj
[Croatian CPC2016] Roj
[Croatian CPC2016] Roj
题目描述
暴风雨将一群蜜蜂吹散到了平面上的不同整数坐标点。它们希望在某一个整数坐标点会合。
所有蜜蜂只能沿同一组允许的方向移动。允许方向是八个方向 N、NW、W、SW、S、SE、E、NE 的一个非空子集,分别代表北、西北、西、西南、南、东南、东、东北。北方为 坐标增大的方向,东方为 坐标增大的方向。
每一步,一只蜜蜂可以沿某个允许方向移动到相邻的整数坐标点。例如,N 表示坐标增加 ,SE 表示增加 。
你可以任意选择会合点。求所有蜜蜂到达同一个会合点所需的总步数的最小值。

输入格式
第一行包含一个整数 (),表示允许的方向数。
第二行包含 个互不相同的方向字符串,用空格分隔。每个字符串均为上文列出的八种之一。
第三行包含一个整数 (),表示蜜蜂的数量。
接下来 行,第 行包含两个整数 (),表示第 只蜜蜂的初始位置。
保证所有初始位置互不相同,且一定存在所有蜜蜂都能到达的整数坐标会合点。
输出格式
输出一个整数,表示所需总步数的最小值。
样例 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