8.3 5G Testing
(RankList for this Question)
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\)

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

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

Log In to solve the Question