Casi Rumba

Warning: This statement was translated using an AI. Results might not be fully accurate or faithful to the original statement. Please report any potential errors on our Discord.

Task

Casi Rumba is a very serious teacher. When the CS class starts, he sits at the teacher's desk and gives the kids work. In the classroom, everyone is focused on solving problems, except for Sebastian. Every time Casi is not looking at him, he puts his headphones on in $1$ second and starts listening to music. Casi, being very strict, does not accept such behavior in his class. When he sees Sebi, he stands up and hastily heads toward the student to scold him, moving one cell per second. Sebi can take his headphones off instantly at any moment, thus avoiding the punishment he was about to receive ($10$ push-ups). Once the kid becomes attentive again, the teacher will move back to the desk in a relaxed manner, at a speed of one cell every $2$ seconds.

The student does not want to be caught inattentive, so given the classroom layout, including the positions of the desks, marked with $B$, the position of the teacher’s desk, marked with $C$, the position of Sebastian, marked with $S$, and the fact that the class lasts $k$ seconds, compute the maximum time the student can spend listening to music without being caught by Casi.

Input data

The first line of the input file casirumba.in contains three integers, $N$, $M$, and $k$, representing the length and width of the classroom, as well as how many seconds the class lasts.

The next $N$ lines contain $M$ characters, representing the layout of the classroom in which the class is held.

Output data

The first line of the output file casirumba.out should contain a single integer, the maximum number of seconds during which Sebastian listens to music.

Constraints and clarifications

• $1 \leq N, M \leq 1 \ 000$
• $1 \leq k \leq 500 \ 000$
• The desk from which Casi starts is marked with $C$, the desks of the other students are marked with $B$, and Sebi’s desk is marked with $S$. Empty cells (which contain nothing and are passable) are marked with 0.
• The characters $C$ and $S$ appear exactly once.
• It is guaranteed that there exists at least one valid path from Casi’s desk to Sebastian.

Example 1

casirumba.in

3 4 10
0 S B B
B 0 0 0
B 0 0 C

casirumba.out

5

Explanation

It takes Casi $3$ seconds to get next to Sebi, during which the student listens to music. When the teacher arrives, he takes his headphones off, making the teacher turn back to the desk. After another $2$ seconds (the time it takes Casi to move one cell back), the student can listen for $1$ more second. This cycle repeats, with Sebi listening for a total of $5$ seconds during the class that lasts $10$ seconds.

Example 2

casirumba.in

4 5 17
B B 0 0 0
0 0 0 B 0
0 B B B 0
0 0 S B C

casirumba.out

13

Explanation

It takes Casi $11$ seconds to get next to Sebi. The student can then listen for $2$ more seconds until the end of the class.