题目描述

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

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

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

输入格式

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

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

括号。

输出格式

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

样例

输入样例

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

输出样例

5

提示

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