CF761F.Dasha and Photos

Dasha decided to have a rest after solving the problem D and began to look photos from previous competitions.

Let's call photos as the matrix with the size n × m, which consists of lowercase English letters.

Some k photos especially interested her, because they can be received from photo-template by painting a rectangular area in a certain color. Let's call such photos special.

More formally the i-th special photo is received from the photo-template by replacing all characters on some rectangle with upper left corner of the cell with coordinates (a__i, b__i) and lower right corner in the cell with coordinates (c__i, d__i) to the symbol e__i.

Dasha asks you to find the special photo so that the total distance from it to all other special photos is minimum. And calculate this distance.

Determine the distance between two photos as the sum of distances between all corresponding letters. The distance between two letters is the difference module of their positions in the alphabet. For example, the distance between letters 'h' and 'm' equals |8 - 13| = 5, because the letter 'h' is the 8-th in the alphabet, the letter 'm' is the 13-th.

达莎在解决完题目 D 后决定休息一下，开始浏览之前比赛的照片。

我们把照片定义为一个大小为 $n \times m$ 的矩阵，其中每个元素均为小写英文字母。

有 $k$ 张照片特别引起了她的兴趣，因为它们均可通过对一张“模板照片”进行一次操作得到：即在模板照片中选取一个矩形区域，并将该区域内所有字符统一替换为某个指定字符。我们将这类照片称为“特殊照片”。

更严格地讲，第 $i$ 张特殊照片是通过如下方式从模板照片得到的：将模板照片中以坐标为 $(a_i, b_i)$ 的单元格为左上角、以坐标为 $(c_i, d_i)$ 的单元格为右下角的矩形区域内所有字符，全部替换为字符 $e_i$。

达莎请你找出一张特殊照片，使其到其余所有特殊照片的总距离最小，并计算该最小总距离。

两张照片之间的距离定义为：对所有对应位置上的字母，分别计算其字母距离，再将所有这些距离求和。两个字母之间的距离定义为它们在英文字母表中位置编号之差的绝对值。例如，字母 'h' 与 'm' 之间的距离为 $|8 - 13| = 5$，因为在英文字母表中，'h' 是第 8 个字母，'m' 是第 13 个字母。

The first line contains three integers n, m, k (1 ≤ n, m ≤ 103, 1 ≤ k ≤ 3·105) — the number of strings in the photo-template, the number of columns and the number of special photos which are interesting for Dasha.

The next n lines contains the string with m length which consists of little Latin characters — the description of the photo-template.

Each of the next k lines contains the description of the special photo in the following format, "a__i b__i c__i d__i e__i" (1 ≤ a__i ≤ c__i ≤ n, 1 ≤ b__i ≤ d__i ≤ m), where (a__i, b__i) — is the coordinate of the upper left corner of the rectangle, (c__i, d__i) — is the description of the lower right corner, and e__i — is the little Latin letter which replaces the photo-template in the described rectangle.

第一行包含三个整数 $n$、$m$、$k$（$1 ≤ n, m ≤ 10^3$，$1 ≤ k ≤ 3·10^5$）—— 分别表示照片模板中的字符串行数、列数，以及达莎感兴趣的特殊照片数量。

接下来的 $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$ 是用于替换照片模板中该矩形区域内所有字符的小写拉丁字母。

In the only line print the minimum total distance from the found special photo to all other special photos.

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

In the first example the photos are following:

bba aaa
bba acc
aaa acc

The distance between them is 10.

在第一个例子中，照片如下：

bba aaa
bba acc
aaa acc

它们之间的距离为 10。