Distant Pastures

Farmer John's farm is an $N \times N$ grid of pastures. Each pasture grows one of two kinds of grass, written with the characters ( and ). For example, the farm might look like this:

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

When Bessie the cow moves to an adjacent pasture (one step north, south, east, or west), the move takes $A$ units of time if the two pastures grow the same kind of grass, or $B$ units of time if they grow different kinds. Whenever Bessie travels from one pasture to another, she always follows a route whose total time is as small as possible.

Consider the minimum travel time between every pair of pastures. Output the largest of these minimum times.

• The first line contains three integers $N$, $A$, and $B$ with $1 \le N \le 30$ and $0 \le A, B \le 10^6$.
• Each of the next $N$ lines contains a string of $N$ parentheses. Together these lines describe the $N \times N$ grid of pastures.

Print a single integer: the largest possible minimum travel time between any pair of pastures, given that Bessie always takes a fastest route.

Think of the pastures as the vertices of a graph whose edges join orthogonally adjacent pastures, each weighted $A$ or $B$. The requested value is the largest shortest-path distance over all pairs of vertices (the weighted diameter of the grid graph).