题目描述

猫娘正在用 $1 \times 1$ 的地砖铺设一面 $n$ 行 $m$ 列的墙壁。墙壁用一个 $01$ 矩阵表示，其中 $1$ 表示该位置可以放砖，$0$ 表示该位置是空洞不能放砖。

请帮猫娘算出：只利用 $1$ 的位置，能铺出的最大正方形的面积是多少？

输入格式

第一行两个整数 $n, m$（$1 \le n, m \le 5000$）。接下来 $n$ 行，每行 $m$ 个用空格隔开的整数（$0$ 或 $1$）。

输出格式

一个整数——最大正方形的面积。

4 5
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

4

3 3
1 1 1
1 1 1
1 1 1

9

样例解释

• 第一个样例中，右下方有一个 $2 \times 2$ 的全 $1$ 区域，面积为 $4$（$3 \times 3$ 的区域被左下角的 $0$ 破坏了）。
• 第二个样例中，整个 $3 \times 3$ 的墙壁都可以铺满，面积为 $3 \times 3 = 9$。

提示说明

• 若矩阵中不存在 $1$，则答案为 $0$。
• 数据规模最大为 $5000 \times 5000$，请使用 $O(nm)$ 的动态规划（$dp_{i,j}$ 表示以 $(i,j)$ 为右下角的最大全 $1$ 正方形边长），注意内存不要开成 $5000 \times 5000$ 的 int 方阵以上。