Trang trại của Farmer John là một lưới đồng cỏ kích thước \(N \times N\), trong đó mỗi đồng cỏ chứa một trong hai loại cỏ khác nhau. Để biểu diễn hai loại cỏ này, ta dùng các ký tự ( và ), vì vậy chẳng hạn trang trại của FJ có thể trông như lưới sau:

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

Khi bò Bessie di chuyển quanh trang trại, cô mất \(A\) đơn vị thời gian để đi từ một đồng cỏ sang một đồng cỏ kề bên (một bước về phía bắc, nam, đông hoặc tây) có cùng loại cỏ, hoặc \(B\) đơn vị thời gian để đi sang một đồng cỏ kề bên có loại cỏ khác. Mỗi khi đi từ một đồng cỏ đến một đồng cỏ xa, Bessie luôn sử dụng một dãy bước mất ít thời gian nhất. Hãy tính lượng thời gian lớn nhất mà Bessie có thể cần khi di chuyển giữa một cặp đồng cỏ nào đó trong trang trại.

Dữ liệu vào

• Dòng 1 chứa ba số nguyên: \(N\) (\(1 \le N \le 30\)), \(A\) (\(0 \le A \le 1\,000\,000\)) và \(B\) (\(0 \le B \le 1\,000\,000\)).
• Các dòng \(1..N+1\): mỗi dòng chứa một chuỗi dấu ngoặc có độ dài \(N\). Tổng thể \(N\) dòng này tạo thành một lưới dấu ngoặc kích thước \(N \times N\).

Dữ liệu ra

• Dòng 1 chứa một số nguyên duy nhất là lượng thời gian lớn nhất mà Bessie có thể dành để di chuyển giữa một cặp đồng cỏ (với điều kiện cô luôn đi theo một lộ trình mất ít thời gian nhất).

Ví dụ

3 1 2
(((
()(
(()

5

Nguồn

USACO 2012 November Contest, Silver — Problem 2: Distant Pastures

Tác giả đề: Brian Dean, 2012.