### 问题描述 小齐的农场是一个 $N \times N$ 的草地网格，每个草地包含两种不同类型的草。为了表示这两种草地，我们使用字符 $($ 和 $)$。 当奶牛贝茜在农场中移动时，她在相邻的同类型草地之间移动需要 $A$ 单位时间，而在相邻的不同类型草地之间移动需要 $B$ 单位时间。无论贝茜从一个草地移动到另一个草地，她总是选择使她花费最短时间的移动路径。请计算在农场的任意两个草地之间，贝茜可能需要花费的最长时间。 ### 输入格式 第 $1$ 行: 三个整数 $N$ $(1 \leq N \leq 30)$, $A$ $(0 \leq A \leq 1,000,000)$, 和 $B$ $(0 \leq B \leq 1,000,000)$。 第 $2$ 行至第 $N+1$ 行: 每行包含长度为 $N$ 的括号字符串。这 $N$ 行共同构成一个 $N \times N$ 的括号网格。 ### 输出格式 第 $1$ 行: 一个整数，指定贝茜在移动到一对草地之间时可能花费的最长时间（假设她总是按照花费最短时间的路径移动）。 ### 样例输入 ``` 3 1 2 ((( ()( (() ``` ### 样例输出 ``` 5 ``` ### 评测数据规模 $1 \leq N \leq 30$，$0 \leq A \leq 1,000,000$，$0 \leq B \leq 1,000,000$。