By Dâmi Henrique, INATEL Brazil
One of the consequences of the truck drivers strike was the lack of gasoline across the country. In Santa Rita do Sapucaí, a city in the south of Minas Gerais, it was no different. Hundreds of cars and motorcycles lined up at the last station with gasoline available to fill their tanks before it drained, it looked like a zombie apocalypse movie scene.
The station has N bombs and in each of them there is a row in a straight line with M veículos (carros ou motos). vehicles (cars or motorcycles). Bellow, there's an illustration of a station with 4 bombs and a row of 2 vehicles per bomb.
Darlan, owner of the station, limited the amount of gasoline that each car could fuel in 25 liters and each bike in 12 liters. Since all vehicles owners in queues were afraid they would never be able to refuel, they would certainly put the maximum gasoline allowed by Darlan.
The local TV station team was live with their drone filming the long lines of vehicles around Darlan’s station when a viewer asked a somewhat random question: "If we take into account that the rows of cars feature a matrix of N lines by M columns, what is the largest amount of gasoline that vehicles in a square of size L will put? Given that in this square there must be at least one vehicle of each type (car and motorcycle)."
The TV crew has no idea how to answer this question and needs your help!
The first line of the input has two integers N, M (1 ≤ N, M ≤ 1000), representing the number of pumps and the number of vehicles queued in each pump. They follow N lines, each containing M characters 'C' or 'M' representing a car or a motorcycle, respectively. After this there will be an integer L (1 ≤ L ≤ 1000), representing the size of the square side that the viewer wishes to know
Display a single integer, the largest possible amount of gasoline that vehicles in a square L will fuel , given that there must be at least one vehicle of each type. If there is no square that characterizes the viewer's doubt, print -1.
Input Sample | Output Sample |
4 2 CM CC MM CC 2 |
87 |
2 2 CC CC 2 |
-1 |
3 5 |
147 |