도서관 이동

도서관은 N x N 격자로 구성되어 있으며, 각 책장에는 두 가지 다른 유형의 책들이 있습니다. 이 두 유형의 책들을 구별하기 위해, 우리는 문자 (  ) 를 사용합니다. 예를 들어 도서관은 다음과 같은 격자로 표현될 수 있습니다:

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

동근이라는 학생이 도서관을 돌아다닐 때, 같은 유형의 책들이 있는 인접한 책장을 이동하는데는 A 시간 단위가 걸리며, 다른 유형의 책들이 있는 인접한 책장으로 이동하는데 B 시간 단위가 걸립니다. 

동근이 한 책장에서 먼 책장으로 이동할 때마다, 그는 항상 최소 시간이 걸리는 경로를 선택합니다. 도서관의 책장 쌍 사이에서 동근이 이동해야 하는 시간이 가장 오래 걸리는 경우를 계산해주세요.

• 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 괄호 격자를 형성한다.

• 1번째 줄 : 동근이 책장 쌍 사이를 돌아다니는데 걸릴 수 있는 최대 시간을 나타내는 단일 정수 (그는 항상 최소한의 시간이 걸리는 경로를 따른다).