D - Maximum Score Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は、あるゲームセンターのイベントに参加しています。会場には N 行 M 列のグリッド状に並んだカードが掲示されており、各カードには 0 から 9 までの整数のポイントが書かれています。グリッドの i 行目 j 列目 (1 \leq i \leq N, 1 \leq j \leq M) のカードのポイントを a_{i,j} と表します。

高橋君は、このグリッドから長方形の領域をちょうど 1 つ選び、その領域内のすべてのカードを獲得します。ここで「長方形の領域」とは、上から 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 を出力してください。

制約

  • 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

1 行目には、グリッドの行数 N、列数 M、ぴったりルールで指定される枚数 K が、スペース区切りで与えられる。

続く N 行のうち i 行目 (1 \leq i \leq N) には、グリッドの i 行目のカードのポイントを左から順に並べた長さ M の文字列 S_i が与えられる。S_i の j 文字目は、グリッドの i 行目 j 列目のカードのポイント a_{i,j}（0 から 9 の整数）を表す。

出力

ぴったりルールを満たす長方形領域が存在する場合は、スコアの最大値を 1 行で出力せよ。存在しない場合は -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

Score : 400 pts

Problem Statement

Takahashi is participating in an event at a game center. At the venue, cards are displayed in a grid of N rows and M columns, and each card has an integer point value from 0 to 9 written on it. The point value of the card at row i, column j (1 \leq i \leq N, 1 \leq j \leq M) of the grid is denoted as a_{i,j}.

Takahashi will select exactly one rectangular region from this grid and obtain all the cards within that region. A "rectangular region" refers to the set of all cards from row r_1 to row r_2 from the top, and from column c_1 to column c_2 from the left (1 \leq r_1 \leq r_2 \leq N, 1 \leq c_1 \leq c_2 \leq M). Letting the number of rows in this region be h = r_2 - r_1 + 1 and the number of columns be w = c_2 - c_1 + 1, the region contains h \times w cards. The sum of the point values written on the obtained cards becomes Takahashi's score.

However, this event has an "exact rule": the number of cards contained in the chosen rectangular region must be exactly K. In other words, the condition h \times w = K must be satisfied.

Find the maximum score Takahashi can achieve. If no rectangular region satisfying the exact rule exists, output -1.

Constraints

  • 1 \leq N \leq 200
  • 1 \leq M \leq 200
  • 1 \leq K \leq N \times M
  • N, M, K are all integers
  • S_i (1 \leq i \leq N) is a string of length M, where each character is one of 0 through 9

Input

N M K
S_1
S_2
\vdots
S_N

The first line contains the number of rows N, the number of columns M, and the number of cards K specified by the exact rule, separated by spaces.

In the following N lines, the i-th line (1 \leq i \leq N) contains a string S_i of length M, representing the point values of the cards in row i of the grid from left to right. The j-th character of S_i represents the point value a_{i,j} (an integer from 0 to 9) of the card at row i, column j of the grid.

Output

If a rectangular region satisfying the exact rule exists, output the maximum score in one line. If no such region exists, output -1.

Sample Input 1

3 4 6
1234
5678
9012

Sample Output 1

30

Sample Input 2

4 5 7
12345
67890
11111
99999

Sample Output 2

-1

Sample Input 3

5 6 12
193842
681937
274619
938271
526184

Sample Output 3

68