Dividing a Rectangle into Three

Time limit2sMemory limit128 MB

Summary

Split a digit grid into three non-overlapping rectangles covering all cells and maximize the product of their digit sums.

Level: Medium5 of 10
Topics: Prefix sum, Brute force, Matrix, Implementation
Solved: No attempts yet

Problem

An $N \times M$ rectangle is filled with $N \times M$ digits.

Divide the rectangle into three non-overlapping smaller rectangles. Every cell must belong to exactly one smaller rectangle, and each smaller rectangle must contain at least one cell.

The sum of a smaller rectangle is the sum of the digits inside it. Find the maximum possible product of the three sums after dividing the given rectangle into three smaller rectangles.

Input

The first line contains the rectangle height $N$ and width $M$ .

The next $N$ lines describe the rectangle from top to bottom. Each line contains exactly $M$ digits.

$N$ and $M$ are positive integers at most $50$ . The rectangle contains at least three cells. Each cell contains one decimal digit.

Output

Print the maximum possible product of the sums of the three smaller rectangles.

Examples3

Example 1
Input
```
1 8
11911103
```
Expected output
```
108
```
Example 2
Input
```
3 3
123
456
789
```
Expected output
```
3264
```
Example 3
Input
```
3 1
7
9
3
```
Expected output
```
189
```