503016 - 作画鬼材

【题目描述】作画鬼材（drawing）NOIAC71 艺术家创作了一张n行m列的像素画。每个像素位置上都有一个颜色，用小写字母来表示（最多s种颜色）。有一天，不知道哪个淘气鬼给这张画创作了k个副本，每个副本都是在原来的像素画的基础上选取一个矩形并覆盖上了同一种新的颜色。 艺术家于是想选择一幅画，使得该画与其他k-1幅画差异度之和最小。 定义差异度为：dis(A,B)=∑(i=1)^n▒∑(j=1)^m▒〖|A(i,j)-B(i,j) 〗| 试计算哪幅画的差异度之和最小。以及这个最小差异度之和是多少。 【输入格式】

第一行为四个正整数n，m，k，s（n，m≤1000，k≤300000，s≤26）。

接下来n行，每行一个长度为 m 的字符串，表示原图。 接下来k行，每行四个正整数和一个字符，x1，y1，x2，y2，col，表示以(x1，y1)为左上角、(x2，y2)为右下角的矩形被涂成了col这个颜色。 【输出格式】 输出一行两个整数，用空格隔开，依次表示最小的差距和选择的画的编号，若有多个答案，输出编号最小的。 【输入样例】 5 7 10 4 cbdadbd bbccada dacdabd cdcacbc baaddad 1 3 5 6 a 1 6 2 6 c 4 1 5 4 b 3 4 5 4 b 2 2 3 7 c 2 4 4 5 d 2 5 3 5 a 4 7 5 7 c 3 1 3 5 c 4 4 5 6 c 【输出样例】 85 7