Pasture Travel Time

Farmer John's farm is represented by an N × N grid where each cell contains one of two types of grass, represented by the characters ( and ). Bessie the cow wishes to travel between pastures. When moving from one pasture to an adjacent one (north, south, east, or west), if the grass type is the same, the time cost is A units; if the grass type is different, the time cost is B units. For any two pastures, Bessie always chooses a path that minimizes the total cost. Your task is to compute the maximum travel time among all pairs of pastures, i.e. the maximum of the shortest path distances.

The cost to move between adjacent pastures is given by:

$$ cost = \begin{cases} A, & \text{if same grass type}\\ B, & \text{if different grass type} \end{cases} $$

Given the grid and the values of A and B, determine the maximum shortest-path distance.

inputFormat

The input starts with a line containing three integers N, A, and B where:

• N is the size of the grid (number of rows and columns).
• A is the cost for moving to an adjacent pasture of the same type.
• B is the cost for moving to an adjacent pasture of a different type.

This is followed by N lines, each containing a string of length N that represents the types of grass in that row of pastures (each character is either ( or )).

outputFormat

Output a single integer representing the maximum of the shortest travel times between any two pastures on the farm.

sample

1 1 2
(

0