Candy Crush

Problem Description

Peanut has recently been obsessed with playing Candy Crush. Candy Crush is a game played by matching candies of similar color together, in order to "pop" them and gain points. The points then add up and contribute to your end score at the end of the level.

Peanut is so obsessed, in fact, that he has created a variant of this game to be used as a programming problem. Yay! In Peanut's variant of Candy Crush, a preset board is given to you and you are supposed to select horizontal or vertical lines of similar color that are at least of length 3 to "pop". When you pop a similarly colored line, you gain (L^2) points where L is the length of the line. Once popped, the candies stay where they are and can be popped again. In other words, the candies do not move AT ALL from turn to turn and the board remains the same.

However, there is a twist. The board starts off with a kind of special blocker. Each of these blockers occupy an entire column and prevent you from popping ANY similarly colored line that involves a candy in one of these blocked off columns. These blockers can only be removed by "popping" a candy beside one of these blockers, where from there on, they will be removed permanently and will not regenerate.

The board will be of size N x N. At the start of the game, the blockers will occupy every column EXCEPT column C. There are three variants of candy in this game, orange candy, green candy and red candy. Each of these are designated by the letters "o", "g" and "r" on the input grid. Also, you are limited to only P pops. Given all these parameters, output the maximum number of points you can gain.

Input

The first line of input will contain three integers, N, C and P.
The following N lines of input will contain N characters each, representing the board using the representation as stated above.

Output

The output should contain one integer, the maximum number of points you can gain by playing optimally.

Limits

Subtask 1 (3%): 1 ≤ N, C ≤ 3. 1 ≤ P ≤ 10. There will only be orange candies on the board.
Subtask 2 (5%): 1 ≤ N, C ≤ 5. 1 ≤ P ≤ 50. There will only be orange and red candies on the board.
Subtask 3 (5%): 1 ≤ N, C ≤ 8. 1 ≤ P ≤ 50.
Subtask 4 (6%): 1 ≤ N, C ≤ 20. 1 ≤ P ≤ 100.
Subtask 5 (7%): 1 ≤ N, C ≤ 50. 1 ≤ P ≤ 100.
Subtask 6 (9%): 1 ≤ N, C ≤ 25. 1 ≤ P ≤ 10⁹
Subtask 7 (10%): 1 ≤ N, C ≤ 50. 1 ≤ P ≤ 10⁹
Subtask 8 (13%): 1 ≤ N, C ≤ 200. 1 ≤ P ≤ 200.
Subtask 9 (20%): 1 ≤ N, C ≤ 200. 1 ≤ P ≤ 10⁹
Subtask 10 (22%): 1 ≤ N, C ≤ 400. 1 ≤ P ≤ 10⁹
Subtask 11 (0%): As per sample testcases.

Sample Input 1

3 2 4
oro
grg
orr

Sample Output 1

36

Sample Input 2

4 2 6
gror
orrg
rrrr
roog

Sample Output 2

82