Ризик
Risk — це настільна гра, що відбувається на карті світу, поділеній на регіони за допомогою кордонів. Кожен регіон контролюється гравцем (або вами, або одним з ваших супротивників). Будь-який регіон, який ви контролюєте, містить позитивну кількість ваших армій.
У кожному ході ви можете переміщувати ваші армії. Кожна з ваших армій може або залишитися на місці, або переміститися з одного регіону в сусідній регіон, який також під вашим контролем. Переміщення виконуються послідовно, у порядку, який ви обираєте. У будь-який момент кожен регіон повинен містити принаймні одну армію.
З стратегічних міркувань важливо переміщати ваші армії в регіони, які межують з регіонами ваших супротивників, і зменшувати кількість армій у ваших регіонах, які повністю оточені іншими регіонами під вашим контролем. Ви прагнете, щоб ваше найслабше місце, тобто прикордонний регіон з мінімальною кількістю армій, було якомога сильнішим. Яка максимальна кількість армій може бути розміщена на ньому після одного ходу?
Вхідні дані
На першому рядку вказано позитивне ціле число: кількість тестових випадків, не більше 100. Далі для кожного тестового випадку:
Один рядок з цілим числом n (1 ≤ n ≤ 100): кількість регіонів.
Один рядок з n цілими числами a_i (0 ≤ a_i ≤ 100): кількість ваших армій у кожному регіоні. Число 0 вказує на те, що регіон контролюється вашими супротивниками, тоді як позитивне число вказує на те, що він під вашим контролем.
n рядків з n символами, де кожен символ — це або 'Y', або 'N'. i-й символ j-го рядка — це 'Y', якщо регіони i та j межують, і 'N' в іншому випадку. Це відношення симетричне, і i-й символ i-го рядка завжди буде 'N'.
У кожному тестовому випадку ви контролюєте принаймні один регіон, і ваші супротивники контролюють принаймні один регіон. Крім того, принаймні один з ваших регіонів межує з принаймні одним з регіонів ваших супротивників.
Вихідні дані
Для кожного тестового випадку:
Один рядок з цілим числом: максимальна кількість армій на вашому найслабшому прикордонному регіоні після одного ходу переміщення.