题目描述

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

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

${S_1 = )()((())))(())}$

${S_2 = ()(()()()((())}$

${S_3 = )))(()()))(())}$

${1111 01234567890123}$

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

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

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

${() (()) ()(()())}$

虽然这些不是：

${)( ())( ((())))}$

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

输入格式

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

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

输出格式

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

样例

输入样例

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

输出样例

3