题目描述

$\red{Farmer John }$的农场由 $\red{N\times N }$的牧场网格组成，每个牧场包含两种不同类型的草中的一种。为了指定这两种类型的草，我们使用字符 $\red{( }$和 $\red{)，}$因此例如 $\red{FJ }$的农场可能 看起来像下面的网格：

$\red{(()) )()( )((( )))) }$当奶牛 $\red{Bessie }$在农场周围走动时，她需要 $\red{A }$单位时间从一个牧场移动到相邻的牧场（向北、向南、向东一步，或西）具有相同的草种，或 $\red{B }$个单位的时 间移动到具有不同草种的相邻牧场。每当 $\red{Bessie }$从一个牧场移动到一个遥远的牧场时，她总是使用一系列花费最少时间的步骤。请计算 $\red{Bessie }$在农场的一对牧场之间旅行时需要花费的最长时间 。

给出一个$\red{n\times n}$的括号矩阵，从一个点走到相邻的同字符点需付出$\red{A}$的代价，到不同字符点需付出$\red{B}$的代价。求所有点对之间最短路的最大值。

输入格式

第 $\red{1 }$行：三个整数：$\red{N (1 <= N <= 30)}$、$\red{A (0 <= A <= 1,000,000) }$和 $\red{B (0 <= B <= 1,000,000)}$。

第 $\red{1..N+1 }$行：每行包含一串长度为 $\red{N }$的括号。这些 $\red{N }$行共同构成一个 $\red{N \times N }$网格

括号。

输出格式

第 $\red{1 }$行：一个整数，指定 $\red{Bessie }$可以在一对牧场之间旅行的最长时间（假设她总是走一条花费最少时间的路线）。

样例

输入样例

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

输出样例

5

提示

$\red{Bessie }$在网格的左上角和右下角之间移动需要 $\red{5 }$个单位的时间。没有其他的牧场让她比这更长时间的旅行。