说明

农夫约翰的农场是一个 $N \times N$ 的牧场网格，每个牧场上种着两种不同种类的草之一。我们用字符 ( 和 ) 来表示这两种草，例如约翰的农场可能看起来像这样：

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

当奶牛贝茜在农场中移动时，从一个牧场移动到相邻的牧场（上、下、左、右一步）需要花费时间：

• 如果两个牧场的草种类相同，花费 $A$ 单位时间。
• 如果两个牧场的草种类不同，花费 $B$ 单位时间。

当贝茜从一个牧场旅行到另一个较远的牧场时，她总是选择一条用时最短的路径。请计算：在所有可能的牧场对之间，按照最短路径行走所需时间的最大值。

输入格式

• 第一行：三个整数 $N$（$1 \le N \le 30$）、$A$（$0 \le A \le 10^6$）和 $B$（$0 \le B \le 10^6$）。
• 接下来的 $N$ 行：每行包含一个长度为 $N$ 的括号字符串，共同构成一个 $N \times N$ 的括号网格。

输出格式

• 一行：一个整数，表示贝茜在任意两个牧场之间旅行所需的最大时间（假设她总是走最短路径）。

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

5 

提示

样例解释

从左上角牧场到右下角牧场需要 $5$ 单位时间。没有其他牧场对需要比这更长的时间。

数据范围

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