Ферма Джона представлена двумерной решеткой пастбищ, каждое из которых содедржит тарву одного из видов (обозначаемых левойц и правой скобками): Например, так: (()) )()( )((( )))) Когда Беси бредет по ферме, ей требуется A единиц времени, чтобы перейти на соседнее пастбище (на север юг, запад или восток) с таким типом травы и B единиц времени, чтобы перейти на соседнее пастбище с другим типом травы. Когда Беси нужно перейти с одного пастбища на другое, она выбирает маршрут, который займет минимальное количество времени. Определите наибольшее количество времени которое потребуется Беси, для перехода между некоторой парой пастбищ фермы.
PROBLEM NAME: distant
Формат входных данных
* Строка 1: Три целых числа: N (1 <= N <= 30), A (0 <= A <= 1,000,000), и B (0 <= B <= 1,000,000).
* Строки 1..N+1: Каждая строка содержит строку скобок длиной N Вместе эти N строк формируют N x N решетку пастбищ.
Формат выходных данных
· Line 1: Одно целое число - максимальное количество времени, которое потребуется Беси между парой пастбищ (Беси всегла выбирает маршрут с минимальным количеством времени)
Примечание
5 единиц времени потребуется Беси чтобы добраться из левого верхнего угла в правый нижний угол решетки. Никакой другой маршрут не займет больше времени.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 1 2
(((
()(
(()
|
5
|