Concurrently Balanced Strings

You are given $K$ strings of parentheses, each of length $N$ ($1 \le K \le 10$, $1 \le N \le 50000$). Label the strings $S_1, S_2, \dots, S_K$; the characters of each string are indexed from $0$ to $N-1$.

A range $i \dots j$ (with $0 \le i \le j \le N-1$) is called concurrently balanced if, for every string $S_1, \dots, S_K$, the substring covering positions $i$ through $j$ is a balanced parenthesis string.

For example, suppose $K = 3$ and the strings are:

S_1 = )()((())))(())
S_2 = ()(()()()((())
S_3 = )))(()()))(())
                1111
      01234567890123

Here the range $3 \dots 8$ is concurrently balanced, because $S_1[3\dots8] = ((()))$, $S_2[3\dots8] = ()()()$, and $S_3[3\dots8] = (()())$ are all balanced. The ranges $10 \dots 13$ and $11 \dots 12$ are concurrently balanced as well.

Count the number of pairs $(i, j)$ such that the range $i \dots j$ is concurrently balanced.

A parenthesis string is balanced when it contains an equal number of ( and ), and every prefix contains at least as many ( as ). For example, these strings are balanced:

• ()
• (())
• ()(()())

while these are not:

• )(
• ())(
• ((())))

• Line 1: two integers $K$ and $N$.
• Lines $2$ through $K+1$: each line contains a parenthesis string of length $N$.

• A single integer: the number of ranges $(i, j)$ that are concurrently balanced.