Description

Farmer John raises a very special breed of cows known for their distinctive appearance, where each cow has a huge circular spot on its hide that, depending on the cow’s orientation, may look like a left parenthesis or a right parenthesis.

One morning, John arranges his cows into $K$ rows, each with $N$ cows ($1 \leq K \leq 10, 1 \leq N \leq 50{,}000$). Since the cows face arbitrary directions, this formation can be described by $K$ parenthesis strings $S_1, ..., S_k$ of length $N$. John is excited to notice that his herd has some “concurrently balanced” ranges, where the range $i...j$ is concurrently balanced only if in each string $S_1, ..., S_k$ the substring over that range is balanced (we will define the meaning of a single parenthesis string being balanced below). For example, if $K = 3$, we have

• $S_1 = \texttt{)()((())))(())}$
• $S_2 = \texttt{()(()()()((())}$
• $S_3 = \texttt{)))(()()))(())}$

Then the range $[3...8]$ is concurrently balanced because $S_1[3...8] = \texttt{((()))}$, $S_2[3...8] = \texttt{()()()}$, and $S_3[3...8] = \texttt{(()())}$. The ranges $[10...13]$ and $[11...12]$ are also concurrently balanced.

Given $K$ parenthesis strings of length $N$, help John count the number of pairs $(i, j)$ such that the range $i...j$ is concurrently balanced across all $K$ strings.

There are several equivalent ways to define “balanced” for a single parenthesis string. Perhaps the simplest is that the total numbers of parentheses must be equal, and for any prefix of the string, the number of left parentheses must be at least as many as the number of right parentheses. For example, the following strings are balanced:

• $\texttt{()}$
• $\texttt{(())}$
• $\texttt{()(()())}$

And these strings are not balanced:

• $\texttt{)(}$
• $\texttt{())(}$
• $\texttt{((())))}$

Given $K$ sequences of length $N$ consisting of parentheses, how many intervals are there such that the corresponding substrings are balanced in all $K$ sequences?

Input Format

The first line contains two integers $K$ and $N$.

The second through the $(K+1)$-th lines: each line contains a parenthesis string of length $N$.

Output Format

The first line contains a single integer, the number of concurrently balanced ranges.

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

3 

Hint

Translated by ChatGPT 5