← 返回题目列表

Codeforces · 761/F

F. 大傻和照片

中文机器翻译题面 查看原题

大傻解决完D题后决定休息一下,开始翻看之前比赛的照片。

我们将照片称为大小为 n × m 的矩阵,由小写英文字母组成。

她对一些 k 照片特别感兴趣,因为可以通过用某种颜色绘制矩形区域来从照片模板中接收这些照片。我们称此类照片为特殊照片。

更正式地,通过用坐标(ai,bi)替换单元格左上角和用坐标(ci,di)单元格右下角的某个矩形上的所有字符替换为符号ei,从照片模板接收第i张特殊照片。

Dasha 要求您找到那张特殊照片,使其与所有其他特殊照片的总距离最小。并计算这个距离。

将两张照片之间的距离确定为所有对应字母之间的距离之和。两个字母之间的距离是它们在字母表中位置的差模。例如,字母“h”和“m”之间的距离等于|8 - 13| = 5,因为字母“h”是字母表中的第 8 位,字母“m”是字母表中的第 13 位。

输入

第一行包含三个整数n、m、k (1 ≤ n, m ≤ 103, 1 ≤ k ≤ 3·105)——照片模板中的字符串数、列数以及Dasha感兴趣的特殊照片的数量。

接下来的 n 行包含长度为 m 的字符串,该字符串由小拉丁字符组成 - 照片模板的描述。

接下来的 k 行包含特殊照片的描述,格式如下:“ai bi ci di ei”(1 ≤ ai ≤ ci ≤ n, 1 ≤ bi ≤ di ≤ m),其中 (ai, bi) — 是矩形左上角的坐标,(ci, di) — 是右下角的描述,ei — 是替换照片模板中的小拉丁字母所描述的矩形。

输出

在唯一的行中打印从找到的特殊照片到所有其他特殊照片的最小总距离。

示例

输入 #1

3 3 2
aaa
aaa
aaa
1 1 2 2 b
2 2 3 3 c

输出 #1

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

输出 #2

59

注意

在第一个示例中,照片如下:

它们之间的距离是 10。