No tags yet

No tag edit access

E. Training with Doors

time limit per test

4 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputCol. Sheffard is going to make a training for Cpt. Plice. The colonel has a polygon containing infinite number of closed doors placed one by one in a row. Initially Cpt. Plice stands in front of the first door. The captain is able to perform the following two commands:

- open the first closed door and go to the front of the next closed door (mark this command as '(' ),
- go to the front of the last of currently opened doors and close it (mark this command as ')' ).

A sequence of commands is valid if the following conditions are met:

- there is at least one opened door when the command ')' should be performed (in particular, the first command shouldn't be ')'),
- all the doors are closed after performing all commands from the sequence (the captain stands in front of the first door).

Col. Sheffard received a template — a rectangular grid with *n* rows and *m* columns where each cell contains one of the commands, i.e. '(' or ')'. The colonel has to choose a training plan for the captain — select a non-empty rectangle from the grid, each row of the rectangle will be an independent training for the captain. The training plan is valid, if each row of the selected rectangle is a valid sequence of commands.

You are to find the number of ways to select a valid training plan for a given grid. The selected rectangle should be continuous, i.e. without holes. Plans are different if they have different positions of their corners even if their contents are the same.

Input

The first line contains two integers *n* and *m* (1 ≤ *n*, *m* ≤ 50000) — number of rows and number of columns in the template respectively. Each of the following *n* lines contains a string with *m* symbols '(' or ')' — commands of the template. The total number of elements in the template doesn't exceed 10^{6}.

Output

Output a single integer — the number of rectangles on the template, corresponding to a valid training plan. Two rectangles with equal content but different positions of corners should be counted both.

Examples

Input

1 5

(()()

Output

3

Input

3 2

()

()

()

Output

6

Input

4 4

()()

()()

)()(

()()

Output

13

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/28/2017 16:56:13 (c4).

Desktop version, switch to mobile version.
User lists

Name |
---|