MATRIX - Count maximum matrices

You are given a matrix A of M rows and N columns, consisting of numbers 0 and 1. For a rectangle in A (sides >= 1), X1 is the number of ones on its sides, X0 is the number of zeros on its sides, and its value is defined as X1 – X0. Let us consider W, the maximum value taken over submatrices of A, and S, the number of submatrices with value W. Your task is to find W and S.

Input

The first line of input contains the number of testcases t (t <= 15). The first line of each testcase contains the numbers M, N (1 <= M, N <= 200) Then M lines follow. In each line, there are N numbers 0 or 1.

Output

For each testcase, you should output a single line with numbers W and S.

Example

Input:
1
5 6
1 1 1 1 1 1
1 0 0 0 0 1
1 0 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1

Output:
18 1

Được gửi lên bởi:Lê Đôn Khuê
Ngày:2005-06-08
Thời gian chạy:2.538s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: GOSU NODEJS PERL6 PYPY RUST SED VB.NET

hide comments
2020-03-20 17:19:55
Tuyen ngu

2020-03-20 13:00:42
nhầm 2 thành 1 quá nhiều đấm AC

Last edit: 2020-03-20 13:29:44
2020-03-19 15:57:23
thangchotuyen
2020-03-17 22:22:43
thằng chó tuyển cmt à
2020-03-16 15:28:20
lưu ý anh em bài này phải dùng ý tưởng quy hoạch động còn nếu dùng thuật toán dịch chuyển là không đúng mô nha
2017-12-26 06:32:17
Thuật toán Kadane sửa công thức chút xíu O(n^3). Có thể có cách nhanh hơn.
cda.dev
2017-12-26 04:15:19
tiếng việt : http://vnoi.info/problems/MATRIX/
Ai làm AC rồi để lại Sol vs nhá
2016-10-05 05:20:10 nguyenngocanh
test đề bài sao ra dc 18 với 1 vậy
2014-05-01 05:57:07 Lưu Tiểu Tiểu
không có đề tiếng việt à
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.