Concurrently Balanced Bracket Intervals

Farmer John has arranged his cows in K lines each containing N cows. Each cow bears a giant spot in the shape of a parenthesis – either a left parenthesis '(' or a right parenthesis ')'. For each line, the arrangement is represented as a string of length N consisting of these parentheses. A range [i, j] (using 0-indexed positions on the prefix sum array) is called balanced for a string if:

• The total number of left and right parentheses are equal.
• For every prefix of the substring, the number of left parentheses is at least as many as the number of right parentheses.

A range is said to be concurrently balanced if it is balanced in all K strings simultaneously.

Formally, define for each string S a prefix sum dp[i] (with dp[0] = 0) where for each position i (1 ≤ i ≤ N) we add +1 if S[i-1] is '(' and -1 if it is ')'. Then a substring from position i+1 to j (i.e. using dp indices i and j with 0 ≤ i < j ≤ N) is balanced if:

Your task is to count the number of pairs (i, j) (with 0 ≤ i < j ≤ N) such that for each of the K lines the corresponding substring is balanced.

Note: If for any of the K strings, the substring is not balanced then the range is not concurrently balanced.

Constraints: 1 ≤ K ≤ 10, 1 ≤ N ≤ 50,000.

inputFormat

The first line contains two integers K and N, the number of strings and the length of each string, respectively.

Then follow K lines, each containing a string of length N consisting solely of characters '(' and ')'.

outputFormat

Output a single integer – the number of pairs (i, j) (with 0 ≤ i < j ≤ N) such that for every string, the substring corresponding to indices i+1 through j is balanced.

sample

1 2
()

1