分数: 400 分
问题陈述
高桥正在游戏中心参加一项活动。在会场,卡片以网格形式展示 N 行和 M 列,每张卡都有一个整数点值 上面写着 0 to 9 。该行牌的点数 i,列 网格的 j (1 \leq i \leq N, 1 \leq j \leq M) 表示为 a_{i,j}.
高桥将从该网格中恰好选择一个矩形区域并获取该区域内的所有卡牌。 “矩形区域”是指行中所有卡片的集合 r_1 到行 r_2 从顶部和从列 c_1 转至专栏 c_2 从左开始(1 \leq r_1 \leq r_2 \leq N, 1 \leq c_1 \leq c_2 \leq M)。令该区域的行数为 h = r_2 - r_1 + 1 和列数为 w = c_2 - c_1 + 1,该区域包含 h \times w 卡。所获得的卡片上所写的分值的总和就是高桥的分数。
然而,这个事件有一个“精确规则”:所选矩形区域中包含的卡片数量必须恰好是 K。换句话说,条件 必须满足 h \times w = K 。
找出高桥可以达到的最高分数。如果不存在满足精确规则的矩形区域,则输出 -1.
约束
- 1 \leq N \leq 200
- 1 \leq M \leq 200
- 1 \leq K \leq N \times M
- N, M, K 均为整数
- S_i (1 \leq i \leq N) 是一个长度为的字符串 M,其中每个字符是以下之一
0通过9
输入
N M K S_1 S_2 \vdots S_N
第一行包含行数 N,列数 M,以及卡片数量 K 由精确规则指定,以空格分隔。
在下面 N 行, i第行 (1 \leq i \leq N) 包含一个字符串 S_i 长度 M,代表该行牌的点数 网格的 i 从左到右。的 j- 第一个字符 S_i 代表点值 a_{i,j} (来自的整数 行中卡的 0 to 9) 网格的 i,列 网格的 j 。
输出
如果存在满足精确规则的矩形区域,则输出一行中的最大分数。如果不存在这样的区域,则输出 -1.
示例输入 1
3 4 6 1234 5678 9012
示例输出 1
30
示例输入 2
4 5 7 12345 67890 11111 99999
示例输出 2
-1
示例输入 3
5 6 12 193842 681937 274619 938271 526184
示例输出 3
68