Maximizing the Fully White Subrectangle

JYY loves puzzle games and has a collection of black‐and‐white puzzle pieces. Each piece is a grid of N rows and a given number of columns W_i (for the i-th piece). Initially, JYY places his S pieces from left to right in the order 1, 2, …, S to form a large rectangle of size N by M, where M = \(\sum_{i=1}^{S} W_i\).

He then discovers that by reordering the puzzle pieces, the maximum area of any subrectangle that is completely white (all cells are white) in the final assembled board might increase.

Your task is to help JYY find the optimal reordering of the pieces such that the area of the largest fully white subrectangle in the resulting grid is maximized. Note that the chosen subrectangle can be located anywhere in the big rectangle, and its rows and columns must be consecutive.

The problem can be summarized as: Given S puzzle pieces (each a grid of N rows and W_i columns of characters '1' (white) or '0' (black)), find the maximum area of a subrectangle (formed by consecutive rows and consecutive columns) such that every cell in the subrectangle is white. You are allowed to reorder the pieces arbitrarily before concatenating them horizontally.

Hint: A common approach to find the maximum white subrectangle in a binary matrix is to use a histogram (stack) based algorithm row by row. Since S is small (e.g. S ≤ 10), enumerating all permutations of pieces is feasible.

The formulas used in this problem include:

\( M = \sum_{i=1}^{S} W_i \)

and the area of a subrectangle defined by height \(h\) and width \(w\) is \( A = h\times w \).

inputFormat

The input begins with two integers S and N — the number of puzzle pieces and the number of rows in each piece.

Then for each of the S pieces, the input is given as follows:

• An integer W_i representing the number of columns in the i-th piece.
• N lines follow, each a string of length W_i consisting only of characters '0' and '1', where '1' represents a white cell and '0' represents a black cell.

The pieces are to be concatenated horizontally in some order (a permutation of the pieces) to form a grid of N rows and M = \(\sum_{i=1}^{S} W_i\) columns.

outputFormat

Output a single integer — the maximum area of a contiguous subrectangle (formed by consecutive rows and consecutive columns) that is completely white, achievable by reordering the pieces optimally.

sample

2 2
3
110
111
2
11
01

6