Рекламный щит

Для рекламы своей новой продукции в Китае одна компания решила разместить на небоскребе рекламный щит. Щит состоит из лампочек, организованных в форме прямоугольной сетки из N строк и M столбцов. В любой момент каждая из лампочек может быть либо включена, либо выключена.

Рекламное сообщение состоит из K иероглифов, которые будут показываться один за другим. Для каждого иероглифа известно, какие лампочки должны быть включены при отображении этого иероглифа. Остальные лампочки должны быть выключены.

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

Для оптимизации работы системы управления необходимо разбить лампочки на минимальное возможное число таких групп. Помогите сотрудникам рекламного отдела компании решить эту задачу.

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

В первой строке входного файла INPUT.TXT заданы числа K, N и M (1 ≤ K, N, M ≤ 100) – количество иероглифов в рекламном сообщении, высота и ширина рекламного щита.

Далее, в K∙N строках идет описание иероглифов. Каждый из K иероглифов задается N строками по M символов в каждой. Все эти строки состоят только из символов «*» и «.», «*» соответствует включенной лампочке, «.» – выключенной.

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

В выходной файл OUTPUT.TXT выведите минимальное число групп, на которое можно разбить лампочки.

Пример

Пояснения к примеру

В приведенном примере можно разбить лампочки на группы следующим образом: две лампочки из первого столбца образуют одну группу, две лампочки из последнего столбца – вторую, а каждая из двух оставшихся лампочек образует отдельную группу.

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]