TopCoder

Thumb 5b3
Nekosyndrome
かわいいは正義!

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

91.7% (11/12)

Description

還記的TIOJ1370--超大鏡框設置嗎?

這次這個神祕的鏡框又回來了>.

不過這次給你的,是一個n*m大小的空中俯視圖,理面有許多障礙物與空地。

障礙物以0代表,空地則以1代表。

現在你想在空地上製作一個盡量大的鏡框,但是鏡框框起的範圍裡不能有障礙物(不然玻璃會破掉Q口Q)

當然了,這次鏡框設置的歸來,絕對不會只有設置鏡框那麼簡單。

因為你發現到,地板是可以交換的@@!

沒錯,經由神秘魔法的幫助,你每次可以將一整行(column↓↑)的地板與另一整行的地板做交換。

現在給你這個空照圖,問你說能做出最大的鏡框有多大!?

Input Format

輸入第一行包含兩數n,m(1<=n<=15000,1<=m<=1500)。
接下來有n行,每行有m個字元,代表這個空照圖。

Output Format

輸出最大可設置的鏡框大小。

Sample Input

10 6
001010
111110
011110
111110
011110
111111
110111
110111
000101
010101

Sample Output

21

Hints

※為了怕你輸入完就Time Limit Exceed,所以建議使用fgets或者getchar()來輸入空照圖。

範例測資解釋:
001010
111110
011110
111110
011110
111111
110111
110111
000101
010101

Problem Source

原TIOJ1550 / Problem Setter: math120908
(adapt from CEOI2009 day2--logs)

Subtasks

For Testdata: 0 ~ 0, Score: 11
For Testdata: 1 ~ 1, Score: 11
For Testdata: 2 ~ 2, Score: 11
For Testdata: 3 ~ 3, Score: 11
For Testdata: 4 ~ 4, Score: 11
For Testdata: 5 ~ 5, Score: 11
For Testdata: 6 ~ 6, Score: 11
For Testdata: 7 ~ 7, Score: 11
For Testdata: 8 ~ 8, Score: 12
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 3000 65536 262144
1 3000 65536 262144
2 3000 65536 262144
3 3000 65536 262144
4 3000 65536 262144
5 3000 65536 262144
6 3000 65536 262144
7 3000 65536 262144
8 3000 65536 262144