Dhaka “Mohanagar” can be shown as a -dimensional grid consisting of rows, and columns. Each cell can be defined as a part of Land or Water .
As a Don, you want to occupy the city. There are some criteria that you must follow to do that.
You can only occupy some area if the area has height and width .
All cells of the selected area should either be Land or Water.
You can select areas multiple times from the grid.
Your selected areas can intersect with each other.
Given the numbers and the grid , you have to answer the maximum number of distinct cells you can possess over the grid.
The test case will contain four integers and separated by spaces where and are the numbers of rows and columns of the grid, and are the height and width of the area you can select.
Next lines will contain characters, which in total represent the grid , Where or where and
Note: and .
For each test case, you have to output an integer which is the maximum number of distinct cells you can possess over the grid.
Check out the samples for clarification.
Input | Output |
---|---|
3 3 2 2 LLL LLW LWW | 4 |
Input | Output |
---|---|
2 4 2 2 LLLW LLLW | 6 |
Explanation of second sample, |