Risk is a board game played on a world map. This world is divided into
regions by borders. Each region is controlled by a player (either you
or one of your opponents). Any region that you control contains a
positive number of your armies.
In each turn, you are allowed to move your armies. Each of your armies
may either stay where it is, or move from a region to a bordering
region under your control. The movements are performed one by one, in
an order of your choice. At all times, each region must contain at
least one army.
For strategic purposes, it is important to move your armies to regions
that border your opponents' regions and minimize the number of armies
on your regions that are totally surrounded by other regions under
your control. You want your weakest link, i.e., the border region with
the minimum number of armies, to be as strong as possible. What is the
maximum number of armies that can be placed on it after one turn?
Input
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 n (1 ≤ n ≤ 100): the number of
regions.
One line with n integers ai (0 ≤ ai ≤ 100): 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.
n lines with n characters, where each character is either `Y' or
`N'. The i-th character of the j-th line is `Y' if
regions i and j border, and `N' otherwise. This
relationship is symmetric and the i-th character of the i-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.
Output
Per test case:
One line with an integer: the maximum number of armies on your weakest
border region after one turn of moving.