Олимпиадный тренинг

Задача . F. Даша и фотографии

Задача

Темы: дп Перебор реализация Структуры данных *2600

Даша решила немного отдохнуть после решения задачи D и стала просматривать фотографии с прошедших олимпиад.

Назовем фотографией матрицу размера n × m, состоящую из строчных латинских букв.

Некоторые k фотографий особенно заинтересовали её, так как их можно было получить из фотографии-шаблона путем покраски прямоугольной области в некоторый цвет. Назовем такие фотографии особенными.

$\text{[math]}$

Более формально i-я особенная фотография получается из фотографии-шаблона путем замены всех символов на некотором прямоугольнике с левым верхним углом в клетке с координатами (a_i, b_i) и с правым нижним углом в клетке с координатами (c_i, d_i) на символ e_i.

Даша просит вас найти особенную фотографию, суммарное расстояние от которой до всех остальных особенных фотографий минимально. И вычислить это расстояние.

Определим расстояние между двумя фотографиями, как сумму расстояний между всеми соответствующими буквами. Расстоянием между двумя буквами является модуль разницы их позиций в алфавите. Например, расстояние между буквами 'h' и 'm' равно |8 - 13| = 5, потому что буква 'h' 8-я в алфавите, а буква 'm' — 13-я.

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

Первая строка содержит три целых числа n, m, k (1 ≤ n, m ≤ 10³, 1 ≤ k ≤ 3·10⁵) — количество строк в фотографии-шаблоне, количество столбцов и количество особенных фотографий заинтересовавших Дашу.

Следующие n строк содержат строку длины m состоящую из маленьких латинских символов — описание фотографии-шаблона.

Каждая из следующих k строк содержат описание особенной фотографии в следующем формате, «a_i b_i c_i d_i e_i» (1 ≤ a_i ≤ c_i ≤ n, 1 ≤ b_i ≤ d_i ≤ m), где (a_i, b_i) — координата левого верхнего угла прямоугольника, (c_i, d_i) — правого нижнего, а e_i — маленькая латинская буква на которую происходит замена в описанном прямоугольнике фотографии-шаблона.

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

В единственную строку выходных данных необходимо вывести минимальное суммарное расстояние от найденной особенной фотографии до всех остальных особенных фотографий.

Примечание

В первом примере фотографии выглядят так:


bba    aaa
bba    acc
aaa    acc

Расстояние между ними равно 10.

Примеры

№	Входные данные	Выходные данные
1	3 3 2 aaa aaa aaa 1 1 2 2 b 2 2 3 3 c	10
2	5 5 3 abcde eabcd deabc cdeab bcdea 1 1 3 4 f 1 2 3 3 e 1 3 3 4 i	59

time 4000 ms
memory 512 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	3

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

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

Загруженные файлы

Нет