| Codeforces Round 394 (Div. 2) |
|---|
| Закончено |
Даша решила немного отдохнуть после решения задачи D и стала просматривать фотографии с прошедших олимпиад.
Назовем фотографией матрицу размера n × m, состоящую из строчных латинских букв.
Некоторые k фотографий особенно заинтересовали её, так как их можно было получить из фотографии-шаблона путем покраски прямоугольной области в некоторый цвет. Назовем такие фотографии особенными.
Более формально i-я особенная фотография получается из фотографии-шаблона путем замены всех символов на некотором прямоугольнике с левым верхним углом в клетке с координатами (ai, bi) и с правым нижним углом в клетке с координатами (ci, di) на символ ei.
Даша просит вас найти особенную фотографию, суммарное расстояние от которой до всех остальных особенных фотографий минимально. И вычислить это расстояние.
Определим расстояние между двумя фотографиями, как сумму расстояний между всеми соответствующими буквами. Расстоянием между двумя буквами является модуль разницы их позиций в алфавите. Например, расстояние между буквами 'h' и 'm' равно |8 - 13| = 5, потому что буква 'h' 8-я в алфавите, а буква 'm' — 13-я.
Первая строка содержит три целых числа n, m, k (1 ≤ n, m ≤ 103, 1 ≤ k ≤ 3·105) — количество строк в фотографии-шаблоне, количество столбцов и количество особенных фотографий заинтересовавших Дашу.
Следующие n строк содержат строку длины m состоящую из маленьких латинских символов — описание фотографии-шаблона.
Каждая из следующих k строк содержат описание особенной фотографии в следующем формате, «ai bi ci di ei» (1 ≤ ai ≤ ci ≤ n, 1 ≤ bi ≤ di ≤ m), где (ai, bi) — координата левого верхнего угла прямоугольника, (ci, di) — правого нижнего, а ei — маленькая латинская буква на которую происходит замена в описанном прямоугольнике фотографии-шаблона.
В единственную строку выходных данных необходимо вывести минимальное суммарное расстояние от найденной особенной фотографии до всех остальных особенных фотографий.
3 3 2
aaa
aaa
aaa
1 1 2 2 b
2 2 3 3 c
10
5 5 3
abcde
eabcd
deabc
cdeab
bcdea
1 1 3 4 f
1 2 3 3 e
1 3 3 4 i
59
В первом примере фотографии выглядят так:
bba aaa
bba acc
aaa acc
Расстояние между ними равно 10.
