Risk#2454
Risk is a board game played on a world map. This world is divided into regions by borders. Each region is controlled either by you or by 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 army may either stay where it is, or move from one region under your control to a neighboring region, also under your control. The movements are performed one by one, in an order you choose. At all times, each region must contain at least one army.
For strategic purposes, it is important to move your armies into regions that border your opponents' regions and to minimize the number of armies in your regions completely surrounded by your other regions. You would like your weakest link—the border region with the fewest armies—to be as strong as possible. What is the maximum number of armies that can be placed in your weakest border region after one turn?
The first line contains a positive integer: the number of test cases, at most . After that, for each test case:
One line with an integer (1 \leq n \leq 100): the number of regions.
One line with integers a_i (0 \leq a_i \leq 100): the number of your armies in each region. A number indicates a region is controlled by your opponents, otherwise it is under your control.
lines with characters each, where each character is either 'Y' or 'N'. The -th character of the -th line is 'Y' if regions and are neighbors, and 'N' otherwise. This relationship is symmetric and the -th character of the -th line is always '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.
For each test case:
One line with an integer: the maximum number of armies in your weakest border region after one turn of movement.
Example 1