复制题目

【题目描述】

定义一个合法的括号序列的权值为每一对匹配的左右括号的下标之差的总和。例如括号序列 $(())()$ 的权值为 $(4-1)+(3-2)+(6-5)=5$。

你有一个 $n \times m$ 的网格，每个格子中有一个括号，你需要从某个格子开始，每次可以向右或向下走一格，并在某个格子结束。将路径上经过的括号顺次写成一个括号序列后，你需要保证它是合法的，且权值最大。

【输入格式】

第一行包含两个正整数 $n,m$。

接下来一个 $n\times m$ 的矩阵表示网格，保证其由 $($ 和 $)$ 组成。

【输出格式】

一个整数，表示最大的权值。若无解输出 $0$。

【样例输入】

3 5
()()(
(())) 
))(()

【样例输出】

9

【数据规模与约定】

大样例

对于前 $10\%$ 的数据，保证 $1\le n,m\le 10$。

对于前 $30\%$ 的数据，保证 $1\le n,m\le 50$。

对于 $100\%$ 的数据，保证 $1\le n,m \le 300$。

【来源】

璃月港算法竞赛 T4.