Figurines
TopCoder TCO2013 Round 1B
Time Limit: 0.1s, Memory Limit: 64MiB
Ели е разположила няколко (потенциално нула) фигури върху правоъгълна дъска с N реда и M колони. Сега Кристина иска да премахне всички фигури от дъската. В едно движение тя може да премахне всички фигури от не повече от R последователни реда или не повече от C последователни колони.

Сега момичето се чуди колко най-малко такива движения са й нужни, така че да премахне всички фигури от дъската.
Вход
На първия ред на стандартния вход ще бъдат зададени четирите цели числа N, M, R, и C – съответно броя редове, броя колони, максималния брой последователни редове, изчистени в едно движение и максималния брой последователни колони, изчистени в едно движение. Следват N реда, всеки съдържащ по M символа от азбуката {'X', '.'}. 'X' означава клетка, върху която има поставена фигура, а '.' – празна клетка.
Изход
На стандартния изход изведете едно цяло число – минималния брой движения, който е достатъчен да се премахнат всички фигури.
Ограничения
  • 1 ≤ RN ≤ 15
  • 1 ≤ CM ≤ 15
Примерен Вход Примерен Изход
5 5 1 2 .X.X. XX..X .XXX. ...X. .X.XX 3
13 15 1 1 XXXXX.XXXX.XXXX ..X...X....X..X ..X...X....X..X ..X...X....X..X ..X...X....X..X ..X...XXXX.XXXX ............... ......X.XXXX... .....XX....X... ....X.X..XXX... ......X....X... ......X....X... ......X.XXXX... 10
В първия пример с едно движение Крис може да премахне всички фигури от един ред, всички фигури от една колона, или всички фигури от две последователни колони. Един начин за изчистване на цялата дъска е с първото движение да се премахнат фигурите от първата и втората колона, с второто – тези от третия ред, и с трето - тези от четвъртата и петата колона. Друго възможно решение с три движения е чрез разчистване само на колони.
Мрън!