먼 목초지

농부 John의 농장은 $N \times N$ 격자 모양의 목초지로 이루어져 있습니다. 각 목초지에는 두 종류의 풀 중 하나가 자라며, 이를 문자 ( 와 ) 로 나타냅니다. 예를 들어 농장은 다음과 같이 생겼을 수 있습니다.

(())
)()(
)(((
))))

소 Bessie가 인접한 목초지(북, 남, 동, 서 중 한 칸)로 이동할 때, 두 목초지에 같은 종류의 풀이 자라면 $A$ 만큼의 시간이 걸리고, 다른 종류의 풀이 자라면 $B$ 만큼의 시간이 걸립니다. Bessie는 한 목초지에서 다른 목초지로 이동할 때 항상 전체 소요 시간이 최소가 되는 경로를 따릅니다.

모든 목초지 쌍에 대해 최소 이동 시간을 생각합니다. 이 최소 이동 시간들 중 가장 큰 값을 출력하세요.

• 첫째 줄에는 세 정수 $N$, $A$, $B$ 가 주어집니다 ($1 \le N \le 30$, $0 \le A, B \le 10^6$).
• 이어지는 $N$ 개의 줄에는 각각 길이 $N$ 의 괄호 문자열이 주어지며, 이 줄들이 모여 $N \times N$ 격자 목초지를 이룹니다.

정수 하나를 출력합니다. Bessie가 항상 가장 빠른 경로를 이용한다고 할 때, 임의의 두 목초지 사이 최소 이동 시간 중 가능한 가장 큰 값입니다.

목초지를 정점으로 하고, 직교로 인접한 목초지를 각각 $A$ 또는 $B$ 의 가중치로 연결한 그래프를 생각하세요. 구하려는 값은 모든 정점 쌍에 대한 최단 경로 거리의 최댓값, 즉 이 격자 그래프의 가중 지름입니다.