← 返回题目列表

AtCoder · awc0048_d

D. 最高分数

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

分数: 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