Taepyeong Villa
One of Lee Chae Ha's first cases at prosecutor Ju Tae Seon's office was a murder at Taepyeong Villa Complex. One of the suspects was the wife, who might have wanted to obtain her husband's insurance money.
However, all the evidence was insufficient — the murder weapon found at the scene did not show her fingerprints, but someone else's. Still, with the intuition of a veteran, the prosecutor guessed that the weapon actually used might have been buried somewhere else.
Tracing footage from CCTV cameras along the road, they suspected the weapon might be on a nearby mountain. Upon arriving, they found a rectangular plot of empty land, divided into \(N\) rows and \(M\) columns. Each cell contained either a sapling or a stone.
The culprit might have buried the weapon in one of these cells. However, they couldn't determine exactly which one. To narrow it down, Lee Chae Ha proposed a hypothesis: "The cell chosen to hide the weapon lies on a row and column where the difference between the number of saplings and stones is at most \(K\)." Though unsure why, Ju Tae Seon didn't ask further, and directly asked Lee Chae Ha to go hide in the nearby wooden house to wait for the culprit to appear, so as to avoid him coming up with more strange reasoning like the hypothesis just now. Still, Lee Chae Ha wanted to know how many cells satisfy that hypothesis.
If what they suspected is correct, tonight, Han Su Jin will appear to end everything she has caused.
Input
- The first line contains three positive integers \(N, M, K \ (1\le N, M \le 10^3; 0\le K\le 10^3)\);
- The next \(N\) lines each contain \(M\) characters, either
Crepresenting a sapling orDrepresenting a stone.
Output
- The number of cells satisfying Lee Chae Ha's hypothesis.
Scoring
- Subtask 1 (50%): \(N, M \le 10^2\).
- Subtask 2 (50%): No additional constraints.
Example
Example 1
input
5 5 1
CDDCD
DDCCC
DDDCD
CCDDC
CDCDC
output
16
Comments