시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 64 MB 94 24 22 35.484%

문제

준규는 화원을 운영중이다. 준규는 엄청난 가치를 지닌 대마꽃를 M개의 행과 N개의 열을 가진 토지에 경작하는데 진욱이가 자꾸 훔쳐가서 고민에 빠졌다. 준규는 진욱이가 훔쳐가지 못하게 꽃 주변을 울타리로 둘러쌓다. 하지만 시간이 지나면서 울타리 몇개가 부서졌다. 진욱이는 이때를 틈타 다시 꽃을 훔지려고 한다.

아래 보이는 그림은 11행 12열의 화원을 나타낸다. 0은 울타리가 없거나 꽃이 심어져 있는 부분을 나타내고 1은 울타리가 있는 곳을 나타낸다. 화원에 들어 오려면 노란색 부분부터 들어와야 한다.

진욱이가 꽃을 훔치러 화원에 들어왔다. 울타리를 요리조리 피해서 들어가는데 이때 상, 하, 좌, 우로 밖에 이동할 수 없다. 진욱이는 파괴적 성향을 지니고 있기 때문에 울타리로 가로막혀 더이상 안으로 접근할 수 없을 때 울타리를 부순다.  진욱이가 되도록 적은 수의 울타리를 부수면서 안으로 들어갈때, 최대한 많이 울타리를 부순 횟수와 , 그때 얻을 수 있는 꽃의 수를 구하여라.

입력

첫째 줄에 테스트 케이스의 수 T (≤ 10) 가 주어진다. 같은 줄에 주어지는 여러개의 정수는 공백으로 구분된다.

각각의 테스트 케이스의 첫째 줄에는 두개의 정수 R, C가 주어진다 (5 ≤ R, C ≤ 1 000)

R은 화원의 행을 나타내고 C는 열의 수를 나타낸다.

두번째 줄부터 R+1번째 줄까지 화원의 정보가 주어진다. 화원은 꽃이 심어질 수 있는 부분인 0 과 울타리가 설치된 1로 이루어져 있다.

화원에는 적어도 하나 이상의 꽃이 심어지는 부분이 있다고 가정한다.

출력

각각의 테스트 케이스에 대해서 2개의 정수를 출력한다. 첫번째 정수는 진욱이가 부수는 최대 울타리의 수이고, 두번째 정수는 그때 얻을 수 있는 꽃의 최대 개수이다. 두 개의 정수는 공백으로 구분한다.

예제 입력

2
11 12
1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 0 0 1
1 0 1 1 1 1 1 1 1 1 0 1
1 0 1 0 0 0 0 1 0 1 0 1
0 0 1 0 1 1 0 0 0 1 0 1
1 0 1 0 1 0 1 0 0 1 0 1
1 0 1 0 1 1 1 0 0 1 0 1
0 0 1 0 0 0 0 0 0 1 0 1
1 0 1 1 1 1 1 1 1 1 0 1
1 0 0 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1
8 12
0 0 0 1 1 1 1 1 1 0 0 0
0 0 0 1 0 0 0 0 1 0 0 0
0 0 0 1 1 1 1 1 1 0 0 0
1 1 1 1 0 0 0 0 1 1 1 1
1 0 1 0 0 0 0 0 0 1 0 1
1 0 1 0 0 0 0 0 0 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 1 1 1 1 1 1 0 0 0

예제 출력

2 1
2 16

힌트

진욱이는 되도록이면 울타리를 부수지 않고 안으로 들어간다.울타리를 부수지 않고 절대로 안으로 들어 갈 수 없을때만 울타리를 부순다.