Tất cả bò của Farmer John đều thuộc một giống rất kỳ lạ, nổi tiếng nhờ vẻ ngoài đặc trưng — trên da mỗi con bò có một đốm khổng lồ hình dấu ngoặc (tùy theo hướng con bò đang quay mặt, đốm này có thể trông giống dấu ngoặc mở hoặc dấu ngoặc đóng).

Một buổi sáng, Farmer John xếp bò thành \(K\) hàng, mỗi hàng có \(N\) con (\(1 \le K \le 10\), \(1 \le N \le 50\,000\)). Những con bò quay mặt về các hướng khá tùy ý, vì vậy cách xếp này có thể được mô tả bằng \(K\) chuỗi dấu ngoặc độ dài \(N\) là \(S_1,\ldots,S_K\). Farmer John vô cùng hào hứng nhận thấy một số đoạn bò "đồng thời cân bằng", trong đó một đoạn bò \(i...j\) chỉ đồng thời cân bằng khi mỗi chuỗi \(S_1,\ldots,S_K\) đều cân bằng trên đoạn đó (định nghĩa về một chuỗi dấu ngoặc cân bằng được trình bày bên dưới). Chẳng hạn, nếu \(K=3\) và ta có:

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

thì đoạn \([3...8]\) đồng thời cân bằng vì \(S_1[3...8]=((()))\), \(S_2[3...8]=()()()\) và \(S_3[3...8]=(()())\). Các đoạn \([10...13]\) và \([11...12]\) cũng đồng thời cân bằng.

Cho \(K\) chuỗi dấu ngoặc có độ dài \(N\), hãy giúp Farmer John đếm số cặp \((i,j)\) sao cho đoạn \(i...j\) đồng thời cân bằng.

Có nhiều cách để định nghĩa thế nào là một chuỗi dấu ngoặc "cân bằng". Có lẽ định nghĩa đơn giản nhất là tổng số dấu ( phải bằng tổng số dấu ), và trong mọi tiền tố của chuỗi, số dấu ( phải không ít hơn số dấu ). Ví dụ, các chuỗi sau đều cân bằng:

()
(())
()(()())

trong khi các chuỗi sau thì không:

)(
())(
((())))

Dữ liệu vào

• Dòng 1 chứa hai số nguyên \(K\) và \(N\).
• Các dòng \(2..K+1\): mỗi dòng chứa một chuỗi dấu ngoặc có độ dài \(N\).

Dữ liệu ra

• Dòng 1 chứa một số nguyên duy nhất là số đoạn đồng thời cân bằng.

Ví dụ

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

3

Nguồn

USACO 2012 November Contest, Gold — Problem 2: Concurrently Balanced Strings

Tác giả đề: Brian Dean, 2012.