#102633. [BZOJ 2633] [Nwerc2010]Risk

有 个阵地，已知我方在每个阵地上的士兵数，若我方士兵不为 则表示该阵地由我方占领，否则为对方占领。某些阵地之间有通道，我们认为士兵可以经过 单位时间从 个阵地移动到相邻（有通道相连）的阵地。对于一个阵地，如果其相邻的阵地中有非我方阵地，则表示其受到威胁，该阵地中我方人数。
现在求：对我方士兵进行一次 个单位的移动（调动），在保证我方不丢失阵地的情况下（即我方每个阵地上的人数不为 ），使得我方所有受到威胁的阵地中人数最少的阵地的人数尽可能多。

On the first line a positive integer: the number of test cases, at most 100. After that per test case: One line with an integer : the number of regions.
One line with integers : the number of your armies on each region. A number 0 indicates that a region is controlled by your opponents, while a positive number indicates that it is under your control.
lines with characters, where each character is either Y or N. The -th character of the -th line is Y if regions and border, and N otherwise. This relationship is symmetric and the -th character of the -th line will always be N. In every test case, you control at least one region, and your opponents control at least one region. Furthermore, at least one of your regions borders at least one of your opponents' regions.

Per test case: One line with an integer: the maximum number of armies on your weakest border region after one turn of moving.

样例输入 #1

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

样例输出 #1

1
4

对于 的数据，满足 ，，。

Nwerc2010