SPOJ in Gyumri

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

   Охраняемый Петром Васильевичем лес представляет собой прямоугольник размером N на M метров, разделенный на квадраты одинакового размера площадью один м². То есть схематично лес можно представить в виде прямоугольной таблицы с N строками и M столбцами. Строки таблицы нумеруются сверху вниз начиная с единицы, а столбцы – слева направо также начиная с единицы. Следовательно, каждому квадрату можно поставить в соответствие пару чисел (X, Y), где X – это номер строки, а Y – номер столбца, на пересечении которых квадрат находится.

   Известно, что на каждом квадрате леса может расти не более одного дерева. По правилам лесничества место для постройки дома должно иметь прямоугольную форму, границы должны проходить по линиям, разделяющим лес на квадраты, а также не может выходить за границы леса. С точки зрения комфорта, Петр Васильевич знает, что площадь места для постройки его будущего дома не может быть меньше S м². Петр Васильевич понимает, что все деревья, находящиеся на выбранном под постройку месте, придется вырубить, а также знает, что вырубка более чем K деревьев недопустима.

   Ваша задача – посчитать количество деревьев в первой строке.

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

   Первая строка содержит четыре целых числа, разделенные одиночными пробелами N, M (2 ≤ N, M ≤ 300), K (0 ≤ K ≤ N * M) и S (1 ≤ S ≤ N * M) соответственно.

   Следующие N строк содержат строковые величины, состоящие из M символов, описывающих лес, j-й символ в i-й по счету строковой величине описывает один квадрат с координатами (i, j). Символ ‘#’(ASCII 35) – на квадрате с координатами (i, j) растет дерево, символ ‘.’(ASCII 46) – на квадрате с координатами (i, j) деревьев нет.

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

   Одно целое число – количество деревьев в первой строке.

Примеры.