8.3 5G Testing

Score: 30pts

Time Limit: 1.00 sec

Rahul is the owner of a telecom company that is currently testing 5G network. His company has \(n\) network towers all across the country but since they’re still in the testing phase there are certain limitations. The tower can only provide network coverage to only one city and the city has to be within a distance \(k\) from the tower. Assume that these cities and towers are present in a grid where each cell can have either a tower or a city. Also, a tower can only provide coverage to the cities that are in the same row as the tower. Help Rahul in finding out the maximum number of cities that he can provide service to.

Constraints

\(1 \leq n \leq 1000\)

\(1 \leq k \leq n\)

\(1 \leq k \leq n\)

Input Format

The first line contains two integers \(n\) and \(k\) that denote the number of towers and the distance a tower can cover respectively

The next \(n\) lines contain \(n\) space-separated characters (each denoting a cell in the grid). T denotes a tower and C denotes a city

The next \(n\) lines contain \(n\) space-separated characters (each denoting a cell in the grid). T denotes a tower and C denotes a city

Output Format

Print the number of cities the towers will be able to provide service to

Example 1

Input:

3 1

T C T

C T C

C C T

Output:

3

Explanation:

Total cities = 5

In row 1, only one city exists thus the tower can provide service to it

In row 2 and 3, there are two cities but only one tower so only one city will get network in both of these rows

3 1

T C T

C T C

C C T

Output:

3

Explanation:

Total cities = 5

In row 1, only one city exists thus the tower can provide service to it

In row 2 and 3, there are two cities but only one tower so only one city will get network in both of these rows