The Don and Mohanagar

Limits 1s, 512 MB

Dhaka “Mohanagar” can be shown as a 22-dimensional grid GG consisting of  NN rows, and MM columns. Each cell can be defined as a part of Land LL or Water WW.

As a Don, you want to occupy the city. There are some criteria that you must follow to do that.

Given the numbers N,M,h,wN, M, h,w and the grid GG, you have to answer the maximum number of distinct cells you can possess over the grid.


The test case will contain four integers N,M,hN, M, h and ww separated by spaces where NN and MM are the numbers of rows and columns of the grid, hh and ww are the height and width of the area you can select.

Next NN lines will contain MM characters, which in total represent the grid GG, Where G[i][j]=LG[i][j] = ‘L’ or G[i][j]=WG[i][j] = ‘W’ \:where (1iN)\: ( 1\le i\le N) and (1jM)(1\le j\le M)

1N,M1001\le N,M\le 100

1h,w1001\le h,w\le100

Note: 1hN1\le h\le N and 1wM1\le w\le M.


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.


3 3 2 2
2 4 2 2

Explanation of second sample,
First, we can take an area of 2*2 (showed using red) this gives us 4 new { (1,1), (1,2), (2,1), (2,2) } cells to the ans. Secondly, we can take another area of 2*2 (showed using blue) this gives us 2 new { (1,3), (2,3) } cells to the ans (2 cells (1,2) and (2,2) were already calculated for the red region). After this, we can’t take any area of 2*2 with given conditions. So our answer is 6.