409556: GYM103630 H Рудольф и вышивка крестиком

H. Рудольф и вышивка крестикомограничение по времени на тест2 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Рудольф с недавнего времени решил пересмотреть свои хобби и увлекся вышиванием. Чтобы вышить очередной шедевр, Рудольфу нужно закупиться нитками. Для этого ему нужно понять, сколько вообще ниток нужно. В его распоряжении есть схема для вышивки, которая представляет собой прямоугольное поле состоящее из символов «.» и «x». Символом «x» отмечены элементы, которые как раз нужно вышивать. Рудольф уже достаточно опытен в этом деле, поэтому знает, что на один символ «x» уходит $$$L$$$ миллиметров ниток. Всем любителям вышивки хорошо известно, что в одном мотке содержится $$$K$$$ метров ниток.

Помогите Рудольфу определить, какое минимально количество мотков ниток нужно приобрести, чтобы их гарантированно хватило для вышивки заданной схемы.

Входные данные

Первая строка содержит целые числа $$$N$$$, $$$M$$$, $$$L$$$, $$$K$$$ ($$$1 \le N, M, K \le 100, 1 \le L \le 10^6$$$) — высота и ширина схемы для вышивки, длина нитки в миллиметрах, требуемая для вышивки одного крестика, а также размер одного мотка ниток в метрах.

Далее следует $$$N$$$ строк по $$$M$$$ символов — описание схемы для вышивки. Каждая строка описание состоит из символов «.» и «x».

Выходные данные

Выведите единственное целое число — минимальное количество мотков ниток, которого гарантированно хватит для вышивки заданной схемы.

ПримерыВходные данные

6 27 99 1
.xxx..xx....xxx..xxxx..xx..
..x..x..x...x..x.x....x..x.
..x..x..x...x..x.x....x..x.
..x..x.xx...xxx..xxx..x..x.
..x..x..x...x....x....x..x.
.xxx..xx.x..x....x.....xx..

Выходные данные

6

Входные данные

3 3 4000 6
...
xxx
...

Выходные данные

2