### 问题描述

小齐的农场是一个 $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$。