题目描述

$\red{Farmer John }$的奶牛都是一个非常奇特的品种，以其独特的外观而闻名$\red{--}$每头奶牛的皮上都标有一个括号形状的巨大斑点（取决于奶牛面对的方向，这可能看起来像左括号或右括号）。

一天早上，$\red{Farmer John }$将他的奶牛排列成 $\red{K }$行，每头 $\red{N }$头奶牛 $\red{(1 <= K <= 10, 1 <= N <= 50,000)}$。奶牛的方向相当随意，所以这个阵容可以用 $\red{K }$个长度为 $\red{N }$的括号 $\red{S_1}$、...、$\red{S_k }$字符串来描述。$\red{Farmer John }$非常兴奋地注意到，他的某些范围内的奶牛是"同时平衡的"，其中只有当字符串 $\red{S_1}$、...、$\red{S_k }$中的每一个在 该范围内平衡时，范围 $\red{i...j }$的奶牛才会同时平衡（我们在下面定义了单个括号平衡的含义）。例如，如果 $\red{K = 3，}$我们有

$\red{S_1 = )()((())))(())}$

$\red{S_2 = ()(()()()((())}$

$\red{S_3 = )))(()()))(())}$

$\red{1111 01234567890123}$

然后范围 $\red{[3...8] }$是同时平衡的，因为 $\red{S_1[3...8] = ((()))}$、$\red{S_2[3...8] = ()()() }$和 $\red{S_3[3 ...8] = (()())}$。范围 $\red{[10...13] }$和 $\red{[11...12] }$也是同时平 衡的。

给定 $\red{K }$个长度为 $\red{N }$的括号串，帮助 $\red{Farmer John }$计算对 $\red{(i,j) }$的数量，以使 $\red{i...j }$的范围同时平衡。

有几种方法可以定义单个括号字符串"平衡"的含义。也许最简单的定义是 $\red{(}$'$\red{s }$和 $\red{)}$'$\red{s }$的总数必须相同，并且对于字符串的任何前缀，$\red{(}$'$\red{s }$和 $\red{)}$'$\red{s }$的数量必须至少一样多。例如，以下字符串都是平衡的：

$\red{() (()) ()(()())}$

虽然这些不是：

$\red{)( ())( ((())))}$

给出$\red{k}$个长度为$\red{n}$的括号序列，问有多少个区间在$\red{k}$个序列中对应的子串均平衡。

输入格式

第 $\red{1 }$行：两个整数，$\red{K }$和 $\red{N}$。

第 $\red{2..K+1 }$行：每行包含一个长度为 $\red{N }$的括号字符串。

输出格式

第 $\red{1 }$行：单个整数，同时平衡范围的数量。

样例

输入样例

3 14 
)()((())))(()) 
()(()()()((()) 
)))(()()))(())

输出样例

3