[Nwerc2010]Risk

有 $n$ 个阵地，已知我方在每个阵地上的士兵数：若我方士兵数不为 $0$ 则表示该阵地由我方占领，否则为对方占领。某些阵地之间有通道，我们认为士兵可以经过 $1$ 单位时间从 $1$ 个阵地移动到相邻（有通道相连）的阵地。对于一个阵地，如果与它相邻的阵地中有非我方阵地，则表示它受到威胁。

现在求：对我方士兵进行一次 $1$ 个单位时间的移动（调动），在保证我方不丢失阵地的情况下（即我方每个阵地上的人数不为 $0$ ），使得我方所有受到威胁的阵地中，人数最少的阵地的人数尽可能多。

输入格式

第一行一个正整数，表示测试数据组数，至多 $100$ 组。之后每组测试数据的格式为：

一行一个整数 $n$ ，表示阵地的数目；
一行 $n$ 个整数 $a_i$ ，表示你在每个阵地上的军队数目。 $0$ 表示该阵地由对手控制，正数表示该阵地由你控制；
接下来 $n$ 行，每行 $n$ 个字符，每个字符是 Y 或 N。第 $j$ 行的第 $i$ 个字符为 Y 表示阵地 $i$ 与阵地 $j$ 相邻，为 N 表示不相邻。这个相邻关系是对称的，且第 $i$ 行的第 $i$ 个字符总是 N。

每组测试数据中，你至少控制一个阵地，对手也至少控制一个阵地；并且至少有一个你的阵地与至少一个对手的阵地相邻。

每组测试数据输出一行一个整数，表示移动一轮之后，你最弱的边境阵地上的军队数目的最大值。

2
3
1 1 0
NYN
YNY
NYN
7
7 3 3 2 0 0 5
NYNNNNN
YNYYNNN
NYNYYNN
NYYNYNN
NNYYNNN
NNNNNNY
NNNNNYN

1
4

本题为 NWERC 2010 试题「Risk」，题面与测试数据整理自 BZOJ 2633。

2
3
1 1 0
NYN
YNY
NYN
7
7 3 3 2 0 0 5
NYNNNNN
YNYYNNN
NYNYYNN
NYYNYNN
NNYYNNN
NNNNNNY
NNNNNYN

1
4