Đồng cỏ xa xôi

Cho lưới $N\times N$, mỗi ô chứa ( hoặc ). Chi phí di chuyển giữa hai ô kề nhau là $A$ nếu cùng loại ký tự, $B$ nếu khác loại. Tìm khoảng cách ngắn nhất lớn nhất giữa mọi cặp ô (đường kính đồ thị).

Dữ liệu vào

• Dòng $1$: Ba số nguyên $N$, $A$, $B$.
• $N$ dòng tiếp: Mỗi dòng $N$ ký tự.

Dữ liệu ra

Một số nguyên — khoảng cách ngắn nhất lớn nhất.

Ràng buộc

• $1\le N\le 30$
• $0\le A,B\le {10}^6$

Ví dụ