Squeaky the Rat has left some barrels of toxic waste from his experiments out on his lawn of N by M units.
Coco the Playful Monkey has tipped the barrels over, resulting in toxic waste spilling all over the lawn.
Toxic waste is dangerous, as they can cause bananas to mutate and then bananas will take over the world.
Luckily, Kraw the Scientific Krow happens to have some extra high grade lead planks of all lengths which can contain the damage. Every lead plank has a width of 1 unit, but each plank can be as long as you want.
Each lead plank, when placed, can overlap other lead planks. However, no lead planks can be placed on any spot where there is no toxic waste as Squeaky the Rat will be angry at you for unnecessarily causing more damage to his lawn.
Kraw the Krow charges you 1 dollar for each lead plank. Find the minimum cost that must be paid to cover all the toxic waste.
The first line of input will contain two integers, N and M
The next N lines of input will contain M characters each. If the character is 'x', it means that there is toxic waste on that spot. If the character is '.', it means there is no toxic waste on that spot.
The output should contain one integer, the minimum amount of money required to cover all the toxic waste.
Subtask 1 (12%): N = 2. 1 ≤ M ≤ 50.
Subtask 2 (8%): There will only be 'x'.
Subtask 3 (19%): N = 3. 1 ≤ M ≤ 5.
Subtask 4 (61%): 1 ≤ N, M ≤ 50.
Subtask 5 (0%): Sample Testcases
3 3 xxx .x. xxx
3
| Subtask | Score |
|---|---|
| 1 | 12 |
| 2 | 8 |
| 3 | 19 |
| 4 | 61 |
| 5 | 0 |