Коровы Фермера Джона различаются по породам и каждая корова помечена гигантским пятном на боку в виде круглой скобки. В зависимости от направления, в котором смотрит корова, эта скобка может быть левой или правой скобкой.
Однажды утром ФД организовал своих коров в K строк по N коров в каждой строке (1 <= K <= 10, 1 <= N <= 50,000). Коровы смотрят в произвольных направлениях, поэтому построение может быть описано как K строк из N символов-скобок. Назовем эти строки S1, S2, :, SK. ФД заметил, что некоторые диапазоны коров "параллельно сбалансированы". Диапазон i..j коров называется "параллельно сьалансированным" тогда и только тогда, когда строки S1,S2,:,SK сбалансированы в этом диапазоне. Например, если K=3 и у нас есть 3 строки
S1 = )()((())))(()) S2 = ()(()()()((()) S3 = )))(()()))(()) 1111 01234567890123
Тогда диапазон [3:8] параллельно сбалансирован, поскольку S1[3...8] = ((())) S2[3...8] = ()()() S3[3...8] = (()())
Диапазоны [10...13] и [11...12] также параллельно сбалансированы.
Ваша задача - посчитать количество сбалансированных диапазонов для заданных K строк длины N.
Строка S называется сбалансированной, если количество левых скобок равно количеству правых и для любого префикса этой строки количество левых скобок не меньше чем количество правых скобок.
Например эти строки сбалансированы () (()) ()(()())
А эти - нет: )( ())( ((())))
PROBLEM NAME: cbs
Формат входных данных
* Строка 1: Два целых числа, K и N.
* Строки 2..K+1: Каждая строка содержит N скобок.
Формат выходных данных
* Строка 1: Одно целое число - количество сбалансированных диапазонов
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 14
)()((())))(())
()(()()()((())
)))(()()))(())
|
3
|