In last month's summer storm, Hotel Pela was flooded! The water damage was extensive, and the owners were desperate to avoid future floods in the hotel. So, they decided to enlist the help of several competitive programmers, and asked them to fix as bigger part of the hotel as possible, with a budget of K Euros.

Hotel Pela consists of N square rooms, each of which has a size of RxR cells. The cells may have varying heights denoted '0'-'9', where '0' is the lowest and '9' is the highest possible height. Some of the cells are called leaky cells, because above each of those cells, there is a leak on the roof of the room. The locations where the roof is leaking water are denoted with 'L'.

The managers of the hotel were desperate and, in order to stop the flooding, they decided to put a tall water container under each leak, covering the whole leaky cell (water containers are always taller than all other cells in the room). However, if a leak on the roof is not fixed, the container below that leak will fill up, and spill water onto the neighboring cells. To prevent this, the programmers needed to choose which leaks to plug (plugging one leak costs 1 Euro). Two cells are neighboring if they share a side, therefore no cell has more than 4 neighbors. Once water has leaked onto a non-leaky cell with height H, it will spread to all neighboring cells that have height <= H.

As you can see, the programmers did an excellent job and Hotel Pela looks awesome. What if solving this problem was your responsibility? Can you write a program that will compute and return the maximum possible number of cells (summed across all rooms) that the hotel can keep dry using the allocated budget? A leaky cell that has been plugged is considered a dry cell. You can choose to use as much or as little of the budget as you wish; specifically, you are not required to use up all the money in the budget.

Input

The first line of input contains three integers: N (1 <= N <= 300), the number of rooms, K (1 <= K <= 3 000), the allocated budget, and R (1 <= R <= 20), the size of the rooms.

The following lines describe each of the rooms: the first R lines describe the first room, then a blank line, followed by the second R lines which describe the second room (if there is one), then a blank line again, and R lines which describe the third room (if there is one), etc. Each of the lines which describe the rooms consists only of the digits 0-9, denoting non-leaky cell heights, and the letter L that denotes leaky cells.

Each room may have between 0 and 10 leaky cells. No two leaky cells will be neighbors one to another.

Output

The output should consist of a single integer: the maximum possible number of cells (summed across all rooms) that can stay dry.

Constraints

Time limit: 2 seconds
Memory limit: 256 megabytes

Examples

input
2 1 4
0123
1234
2345
3L56

L876
8765
7654
6543

output
20

input
1 1 2
9L
L9

output
1

In the first test case, If the leak in the first room is not plugged, the following non-leaky cells will be flooded:

    ***3
    ***4
    ***5
    *L*6
Of course, the leaky cell is also flooded.

If the leak in the second room is not plugged, the leak will flood the entire room! Since the budget only has money for one plug, it's better to plug the leak in the second room. Therefore, the entire second room will remain dry (4 * 4 = 16 cells), and the 4 cells of the first room shown above will also remain dry. Therefore, the total number of dry cells in the hotel will be 20.

Scoring

- In test cases worth at least 10% of all points, there will be exactly one room (i.e., N = 1).

- In test cases worth an additional 20% of all points, the total number of leaks in all rooms will be less than 20.

- In test cases worth an additional 20% of all points, there will be at most one leak per room.