题目描述

有 $n$ 个阵地，已知我方在每个阵地上的士兵数，若我方士兵不为 $0$ 则表示该阵地由我方占领，否则为对方占领。

某些阵地之间有通道，我们认为士兵可以经过 $1$ 单位时间从 $1$ 个阵地移动到相邻（有通道相连）的阵地。对于一个阵地，如果其相邻的阵地中有非我方阵地，则表示其受到威胁，该阵地中我方人数。

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

输入格式

第一行是一个正整数 $T$（$T\le 100$），表示有 $T$ 组数据组数

在每个测试用例中：

一行整数 $n$：区域的数量。 一行 $n$ 个整数 $a_{i}$：每个区域上的军队数量。数字0表示该区域被对手控制，正数表示该区域由你控制。

一共 $n$ 行，每行 $n$ 个字符，每个字符要么是Y，要么是N。第 $i$ 行第 $j$ 个字符为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

数据规模与约定

对于 $100\%$ 的数据，满足 $1 \leq n \leq 100$，$0 \leq a_{i} \leq 100$，$1 \leq$ 数据组数 $\leq 100$。

题目来源

Nwerc2010