← 返回题目列表

AtCoder · typical90_bk

063. 单色子网格(★4)

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

配点: 4 点

問題文

縦 H 行、横 W 我有一个列网格,从顶部开始 由 i 行,从左起 j 选择列中的方块。 由 (i, j) 代表。鳟鱼 (i, j) 是一个整数 写入 P_{i, j} 。

现在,从这个网格(不一定是连续的)1 有多于一行 1 可以通过选择多于一列并满足以下条件来创建的“部分网格”。良好的子网格 它被称为。

条件 选定的行 i_1, i_2, \dots, i_A \ (1 \leq i_1 < i_2 < \dots < i_A \leq H) 并选择该列 j_1, j_2, \dots, j_B \ (1 \leq j_1 < j_2 < \dots < j_B \leq W) 然后质量 (i_a, j_b) \ (1 \leq a \leq A, 1 \leq b \leq B) 中写入的所有整数都是相同的。

找到一个好的子网格的最大可能大小。
但是 A 行/ 由B 列组成的子网格的大小为 假设它是 A \times B 。

制約

  • 1 \leq H \leq 8
  • 1 \leq W \leq 10000
  • 1 \leq P_{i, j} \leq HW
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

H W
P_{1, 1} P_{1, 2} \cdots P_{1, W}
P_{2, 1} P_{2, 2} \cdots P_{2, W}
\vdots
P_{H, 1} P_{H, 2} \cdots P_{H, W}

出力

请输出良好子网格的最大可能尺寸。


入力例 1

4 6
1 1 1 1 1 2
1 2 2 2 2 2
1 2 2 3 2 3
1 2 3 2 2 3

出力例 1

6

\{2, 3\} 线和 \{2, 3, 5\} 通过选择列可获得大小 6 的子网格覆盖了所有正方形,如下所示。 2 。

. . . . . .
. 2 2 . 2 .
. 2 2 . 2 .
. . . . . .

因此,这个子网格是一个很好的子网格,因为没有比这个更好的子网格了。 6 。


入力例 2

3 3
1 2 3
4 5 6
7 8 9

出力例 2

1

入力例 3

5 3
7 7 7
7 7 7
7 7 7
7 7 7
7 7 7

出力例 3

15