시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 73 15 7 17.500%

문제

크기가 r×c인 행렬이 주어진다. 행렬의 각 원소는 0 또는 1이다. 행렬이 수행할 수 있는 연산은 원소 하나를 뒤집는 것이다. (0을 1로, 1을 0으로) 상근이는 다음과 같은 조건을 만족하는 행렬로 바꾸려고 한다.

  1. 각 행에 있는 1의 개수는 모두 같아야 한다.
  2. 각 열에 있는 1의 개수는 모두 같아야 한다.

입력으로 주어진 행렬을 위의 조건을 만족하는 행렬로 만드는데 필요한 연산의 최소 횟수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T(≤1000)가 주어진다.

각 테스트 케이스의 첫째 줄에는 두 정수 r과 c가 주어진다. (1 ≤ r, c ≤ 40) r은 행의 수, c는 열의 수이다. 다음 r개 줄에는 c개의 정수가 주어지며, 행렬의 정보이다.

출력

각 테스트 케이스마다 "Case #: R"을 출력한다. #는 테스트 케이스의 번호이고, R은 입력으로 주어진 행렬을 문제의 조건에 맞는 행렬로 바꾸는데 필요한 연산의 최소 횟수이다. 불가능한 경우에는 R에 -1을 출력한다.

예제 입력 1

3
2 3
111
111
3 3
011
011
011
2 3
001
000

예제 출력 1

Case 1: 0
Case 2: 3
Case 3: 1
W3sicHJvYmxlbV9pZCI6IjU2MjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMTRcdWM3NzRcdWIxMDhcdWI5YWMgXHVkNTg5XHViODJjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQwNmNcdWFlMzBcdWFjMDAgciZ0aW1lcztjXHVjNzc4IFx1ZDU4OVx1YjgyY1x1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1ZDU4OVx1YjgyY1x1Yzc1OCBcdWFjMDEgXHVjNmQwXHVjMThjXHViMjk0IDAgXHViNjEwXHViMjk0IDFcdWM3NzRcdWIyZTQuIFx1ZDU4OVx1YjgyY1x1Yzc3NCBcdWMyMThcdWQ1ODlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM1ZjBcdWMwYjBcdWM3NDAgXHVjNmQwXHVjMThjIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWI0YTRcdWM5ZDFcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiAoMFx1Yzc0NCAxXHViODVjLCAxXHVjNzQ0IDBcdWM3M2NcdWI4NWMpIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVkNTg5XHViODJjXHViODVjIFx1YmMxNFx1YWZiOFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+XHVhYzAxIFx1ZDU4OVx1YzVkMCBcdWM3ODhcdWIyOTQgMVx1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgXHViYWE4XHViNDUwIFx1YWMxOVx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YWMwMSBcdWM1ZjRcdWM1ZDAgXHVjNzg4XHViMjk0IDFcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IFx1YmFhOFx1YjQ1MCBcdWFjMTlcdWM1NDRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVkNTg5XHViODJjXHVjNzQ0IFx1YzcwNFx1Yzc1OCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1ZDU4OVx1YjgyY1x1Yjg1YyBcdWI5Y2NcdWI0ZGNcdWIyOTRcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YzVmMFx1YzBiMFx1Yzc1OCBcdWNkNWNcdWMxOGMgXHVkNjlmXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUKCZsZTsxMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YzgxNVx1YzIxOCByXHVhY2ZjIGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IHIsIGMgJmxlOyA0MCkgclx1Yzc0MCBcdWQ1ODlcdWM3NTggXHVjMjE4LCBjXHViMjk0IFx1YzVmNFx1Yzc1OCBcdWMyMThcdWM3NzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyByXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBjXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1ZDU4OVx1YjgyY1x1Yzc1OCBcdWM4MTVcdWJjZjRcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgJnF1b3Q7Q2FzZSAjOiBSJnF1b3Q7XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gI1x1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yzc3NFx1YWNlMCwgUlx1Yzc0MCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1ZDU4OVx1YjgyY1x1Yzc0NCBcdWJiMzhcdWM4MWNcdWM3NTggXHVjODcwXHVhYzc0XHVjNWQwIFx1YjlkZVx1YjI5NCBcdWQ1ODlcdWI4MmNcdWI4NWMgXHViYzE0XHVhZmI4XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWM1ZjBcdWMwYjBcdWM3NTggXHVjZDVjXHVjMThjIFx1ZDY5Zlx1YzIxOFx1Yzc3NFx1YjJlNC4gXHViZDg4XHVhYzAwXHViMmE1XHVkNTVjIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBSXHVjNWQwIC0xXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1NjI4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQmluYXJ5IE1hdHJpeCAyIiwiZGVzY3JpcHRpb24iOiI8cD5Zb3UgYXJlIGdpdmVuIGEgbWF0cml4IG9mIHNpemUgciB4IGMgLiBFYWNoIG9mIHRoZSBlbGVtZW50cyBjYW4gYmUgZWl0aGVyIDAgb3IgMS4gSW4gZWFjaCBvcGVyYXRpb24geW91IGNhbiBmbGlwIGFueSBlbGVtZW50IG9mIHRoaXMgbWF0cml4LCBpLmUuIGNvbnZlcnQgMCB0byAxIG9yIGNvbnZlcnQgMSB0byAwLiBZb3VyIGdvYWwgaXMgdG8gY29udmVydCB0aGUgbWF0cml4IHN1Y2ggdGhhdCAtJm5ic3A7PFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+RWFjaCBvZiB0aGUgcm93cyB3aWxsIGhhdmUgdGhlIHNhbWUgbnVtYmVyIG9mIDFzIGFuZCZuYnNwOzxcL2xpPlxyXG5cdDxsaT5FYWNoIG9mIHRoZSBjb2x1bW5zIHdpbGwgaGF2ZSB0aGUgc2FtZSBudW1iZXIgb2YgMXMuJm5ic3A7PFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+V2hhdCBpcyB0aGUgbWluaW11bSBudW1iZXIgb2Ygb3BlcmF0aW9ucyByZXF1aXJlZCB0byBhY2hpZXZlIHRoaXM/Jm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbnB1dCBzdGFydHMgd2l0aCBhIHBvc2l0aXZlIGludGVnZXIgVCAofjEwMDApIHdoaWNoIGluZGljYXRlcyB0aGUgbnVtYmVyIG9mIGlucHV0cy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBjYXNlIHN0YXJ0cyB3aXRoIHR3byBpbnRlZ2VycyBtIGFuZCBuICgxICZsdDs9IHIsIGMgJmx0Oz0gNDApLCBoZXJlIHIgaXMgdGhlIG51bWJlciBvZiByb3dzIGFuZCBjIGlzIHRoZSBudW1iZXIgb2YgY29sdW1ucyBvZiB0aGUgbWF0cml4LiBFYWNoIG9mIHRoZSBuZXh0IG0gbGluZXMgd2lsbCBoYXZlIG4gaW50ZWdlcnMgZWFjaCwgZWl0aGVyIDAgb3IgMS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCAmbGRxdW87Q2FzZSAjOiBSICZyZHF1bzsgaW4gYSBzaW5nbGUgbGluZSwgd2hlcmUgIyB3aWxsIGJlIHJlcGxhY2VkIGJ5IGNhc2UgbnVtYmVyIGFuZCBSIHdpbGwgYmUgcmVwbGFjZWQgYnkgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHN0ZXBzIHJlcXVpcmVkIHRvIGFjaGlldmUgdGhlIHRhcmdldCBtYXRyaXguIFJlcGxhY2UgUiBieSAtMSBpZiBpdCBpcyBub3QgcG9zc2libGUgdG8gcmVhY2ggdGFyZ2V0IG1hdHJpeC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=