题目描述

给定一个仅由 0 和 1 组成的矩阵 $A$，它有 $N$ 行、$M$ 列。

矩阵的行和列都从 $0$ 开始编号，记第 $i$ 行第 $j$ 列的元素为 $A_{i,j}$。

由矩阵 $A$ 构造出一个更大的矩阵 $B$：

• 在纵向上重复 $R$ 次；
• 在横向上重复 $C$ 次。

于是矩阵 $B$ 有 $N \cdot R$ 行、$M \cdot C$ 列，并满足：

其中：

• $0 \le i < N \cdot R$
• $0 \le j < M \cdot C$

我们称矩阵 $B$ 中的一个矩形为如下形式的一组单元格：

选择两个行下标 $r_1, r_2$ 和两个列下标 $c_1, c_2$，满足：

该矩形包含所有满足行号在 $[r_1, r_2]$、列号在 $[c_1, c_2]$ 范围内的单元格。

请编写程序 matrix，求出矩阵 $B$ 中仅由 1 组成的矩形的最大面积（即单元格数量）。

输入格式

第一行输入四个整数 $N, M, R, C$。

接下来 $N$ 行，每行输入一个长度为 $M$ 的仅由字符 0 和 1 构成的字符串，表示矩阵 $A$。

输出格式

输出一个整数，表示所求的最大面积。

数据范围

• $1 \le N, M \le 2000$
• $1 \le R, C \le 10^6$

子任务

只有通过某个子任务以及其所有依赖子任务的全部测试点，才能获得该子任务的分数。

样例

输入

3 4 2 3
0110
1111
0101

输出

12

样例解释

矩阵 $B$ 的大小为 $N \cdot R = 6$ 行、$M \cdot C = 12$ 列，因此它是：

011001100110
111111111111
010101010101
011001100110
111111111111
010101010101

其中一个最大面积的全 1 矩形面积为 $12$。