Problem : 352 - F. 小紫愛畫矩形

Problem Statistics

Solved Member: 5　　Submission: 23　　User Tried: 8

Statement:

小紫是個有點害羞的平凡高中生，她有時會到處畫矩形。
小紫喜歡到處畫一些方塊，就像是用Windows 7電腦時，按住左鍵從左上往右下拉過去拉出一個藍色方塊的感覺一樣，~~因為我沒梗惹~~ ，小紫不知道為什麼很喜歡畫方塊，但她有一個很怪異的癖好，那就是她希望她畫的長方形是單色der，因為她覺得一個長方形有那麼多顏色感覺很花。
某天，小紫走到了一面牆，碰巧這面牆也是個矩形。上面有很多方塊，且只有黑、白兩種顏色。吃飽太閒的小紫決定發揮她的專長：畫長方形！她決定找一塊白色的區域，並在這個區域上畫長方形。但是，在路邊亂塗鴉總是有些沒良心，因此小紫決定只畫一個長方形。既然只能畫一個，那麼當然是畫越大的越好。但就這樣能畫多大就畫多大好像也有點沒良心，因此她決定要在這面牆上所有可以畫的長方形中，挑面積第二大的長方形來畫，但小紫發現這個問題有點困難，因此她想請問聰明的你，在這面牆中所有畫的長方形中，面積第二大的那個長方形面積是多少呢？
Note:所謂的「面積第二大」是指將所有可能的長方形的面積列出來後，由大到小排序，這個數列的第二項就是所謂的面積第二大，也就是說第二大的面積有可能與第一大的面積一樣大。

Input:Output:

第一行有一個整數t，表示再來有幾筆測試資料。
每筆測試資料的第一行有兩個整數n, m，表示這面牆的大小。
接下來的n行每行有m個以空格隔開的整數，第i行的第j的數字aij表示那個方格的顏色，1表示白色，0表示黑色。

對每筆測試資料，請輸出一個你覺得是答案的整數。如果沒辦法畫出兩種以上的矩形，那就輸出”-1”(不含引號)。

Sample Input:Sample Output:

2
2 3
1 1 0
1 1 1
3 3
0 0 0
0 1 0
0 0 0

3
-1

HINT:

在第一筆測資中，所有能被畫出的矩形中面積最大的是4，面積次大的是3。
在第二筆測資中，只能會出一個面積為1的矩形。

20% t = 5、1 <= n, m <= 50
20% t = 5、1 <= n, m <= 200
60% t = 5、1 <= n, m <= 1,000

Source:

2014 延平校內賽

Problem Setter

rilak

Testdata:

Test	Time	Memory	Score
0	1000ms	262144kb
1	1000ms	262144kb	20
2	1000ms	262144kb	20
3	4000ms	262144kb	20
4	4000ms	262144kb	20
5	4000ms	262144kb	20