시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 95 33 20 31.746%

문제

요즘 선풍적으로 팔리는 카드 중 하나는 앞면의 소녀시대가 새겨진 카드이다. 지원이와 항승이는 돈을 모아서 이 카드를 R*16개 사서 R*16 행렬로 나란히 정렬하여 놓았다. 그리고 평소 소녀시대에 환장하는 항승이는 모든 카드를 소녀시대가 그려져있는 앞면으로 놔둔채 흐뭇하게 감상하고 있었다.

하지만 소녀시대 중 한 멤버를 지독히 싫어하던  지원이는 그 멤버가 새겨진 카드들을 뒤집어 안 보이게하길 원하고 있다.

지원이는 카드 뒤집기 능력이 뛰어나 한 번에 가로나 세로로 연속된 카드들을 뒤집을 수 있다. 하지만 항승이가 잠시 홀려있는 상태에 있을 때 순식간에 뒤집어야하기 때문에 뒤집는 횟수를 최소한 줄이려 한다. (뒤집는 카드 수가 아닌 뒤집는 연산의 수인 것에 주의한다) 이런 지원이의 고민을 도와주자.

입력

첫 번째 줄에 카드 행의 수인 R (1 ≤ R ≤ 50)이 주어진다. 다음 R개의 줄에 길이가 16인 '0' 또는 '1'로 구성된 문자열이 주어진다. '0'은 지원이가 싫어하지 않는 멤버가 그려져 있는 카드, '1'은 지원이가 싫어하는 멤버가 그려져 있는 카드이다.

출력

뒤집는 연산의 최소 개수를 출력한다.

예제 입력 1

5
0000111111110000
0010000000000000
1101111111111111
0010000000000000
0000000000000000

예제 출력 1

3

힌트

W3sicHJvYmxlbV9pZCI6IjE2OTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI0YTRcdWM5ZDFcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzY5NFx1Yzk5OCBcdWMxMjBcdWQ0OGRcdWM4MDFcdWM3M2NcdWI4NWMgXHVkMzE0XHViOWFjXHViMjk0IFx1Y2U3NFx1YjRkYyBcdWM5MTEgXHVkNTU4XHViMDk4XHViMjk0IFx1YzU1ZVx1YmE3NFx1Yzc1OCBcdWMxOGNcdWIxNDBcdWMyZGNcdWIzMDBcdWFjMDAgXHVjMGM4XHVhY2E4XHVjOWM0IFx1Y2U3NFx1YjRkY1x1Yzc3NFx1YjJlNC4gXHVjOWMwXHVjNmQwXHVjNzc0XHVjNjQwIFx1ZDU2ZFx1YzJiOVx1Yzc3NFx1YjI5NCBcdWIzYzhcdWM3NDQgXHViYWE4XHVjNTQ0XHVjMTFjIFx1Yzc3NCBcdWNlNzRcdWI0ZGNcdWI5N2MgUioxNlx1YWMxYyBcdWMwYWNcdWMxMWMgUioxNiBcdWQ1ODlcdWI4MmNcdWI4NWMgXHViMDk4XHViNzgwXHVkNzg4IFx1YzgxNVx1YjgyY1x1ZDU1OFx1YzVlYyBcdWIxOTNcdWM1NThcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWQzYzlcdWMxOGMgXHVjMThjXHViMTQwXHVjMmRjXHViMzAwXHVjNWQwIFx1ZDY1OFx1YzdhNVx1ZDU1OFx1YjI5NCBcdWQ1NmRcdWMyYjlcdWM3NzRcdWIyOTQgXHViYWE4XHViNGUwIFx1Y2U3NFx1YjRkY1x1Yjk3YyBcdWMxOGNcdWIxNDBcdWMyZGNcdWIzMDBcdWFjMDAgXHVhZGY4XHViODI0XHVjODM4XHVjNzg4XHViMjk0IFx1YzU1ZVx1YmE3NFx1YzczY1x1Yjg1YyBcdWIxOTRcdWI0NTRcdWNjNDQgXHVkNzUwXHViYjQ3XHVkNTU4XHVhYzhjIFx1YWMxMFx1YzBjMVx1ZDU1OFx1YWNlMCBcdWM3ODhcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU1OFx1YzljMFx1YjljYyBcdWMxOGNcdWIxNDBcdWMyZGNcdWIzMDAgXHVjOTExIFx1ZDU1YyBcdWJhNjRcdWJjODRcdWI5N2MgXHVjOWMwXHViM2M1XHVkNzg4IFx1YzJlYlx1YzViNFx1ZDU1OFx1YjM1OCZuYnNwOyBcdWM5YzBcdWM2ZDBcdWM3NzRcdWIyOTQgXHVhZGY4IFx1YmE2NFx1YmM4NFx1YWMwMCBcdWMwYzhcdWFjYThcdWM5YzQgXHVjZTc0XHViNGRjXHViNGU0XHVjNzQ0IFx1YjRhNFx1YzlkMVx1YzViNCBcdWM1NDggXHViY2Y0XHVjNzc0XHVhYzhjXHVkNTU4XHVhZTM4IFx1YzZkMFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzljMFx1YzZkMFx1Yzc3NFx1YjI5NCBcdWNlNzRcdWI0ZGMgXHViNGE0XHVjOWQxXHVhZTMwIFx1YjJhNVx1YjgyNVx1Yzc3NCBcdWI2ZjBcdWM1YjRcdWIwOTggXHVkNTVjIFx1YmM4OFx1YzVkMCBcdWFjMDBcdWI4NWNcdWIwOTggXHVjMTM4XHViODVjXHViODVjIFx1YzVmMFx1YzE4ZFx1YjQxYyBcdWNlNzRcdWI0ZGNcdWI0ZTRcdWM3NDQgXHViNGE0XHVjOWQxXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWQ1NmRcdWMyYjlcdWM3NzRcdWFjMDAgXHVjN2EwXHVjMmRjIFx1ZDY0MFx1YjgyNFx1Yzc4OFx1YjI5NCBcdWMwYzFcdWQwZGNcdWM1ZDAgXHVjNzg4XHVjNzQ0IFx1YjU0YyBcdWMyMWNcdWMyZGRcdWFjMDRcdWM1ZDAgXHViNGE0XHVjOWQxXHVjNWI0XHVjNTdjXHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWI0YTRcdWM5ZDFcdWIyOTQgXHVkNjlmXHVjMjE4XHViOTdjIFx1Y2Q1Y1x1YzE4Y1x1ZDU1YyBcdWM5MDRcdWM3NzRcdWI4MjQgXHVkNTVjXHViMmU0LiAoXHViNGE0XHVjOWQxXHViMjk0IFx1Y2U3NFx1YjRkYyBcdWMyMThcdWFjMDAgXHVjNTQ0XHViMmNjIFx1YjRhNFx1YzlkMVx1YjI5NCBcdWM1ZjBcdWMwYjBcdWM3NTggXHVjMjE4XHVjNzc4IFx1YWM4M1x1YzVkMCBcdWM4ZmNcdWM3NThcdWQ1NWNcdWIyZTQpIFx1Yzc3NFx1YjdmMCBcdWM5YzBcdWM2ZDBcdWM3NzRcdWM3NTggXHVhY2UwXHViYmZjXHVjNzQ0IFx1YjNjNFx1YzY0MFx1YzhmY1x1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2U3NFx1YjRkYyBcdWQ1ODlcdWM3NTggXHVjMjE4XHVjNzc4IFIgKDEgJmxlOyBSICZsZTsgNTApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIFJcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWUzOFx1Yzc3NFx1YWMwMCAxNlx1Yzc3OCAmIzM5OzAmIzM5OyBcdWI2MTBcdWIyOTQgJiMzOTsxJiMzOTtcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDFjIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICYjMzk7MCYjMzk7XHVjNzQwIFx1YzljMFx1YzZkMFx1Yzc3NFx1YWMwMCBcdWMyZWJcdWM1YjRcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YmE2NFx1YmM4NFx1YWMwMCBcdWFkZjhcdWI4MjRcdWM4MzggXHVjNzg4XHViMjk0IFx1Y2U3NFx1YjRkYywgJiMzOTsxJiMzOTtcdWM3NDAgXHVjOWMwXHVjNmQwXHVjNzc0XHVhYzAwIFx1YzJlYlx1YzViNFx1ZDU1OFx1YjI5NCBcdWJhNjRcdWJjODRcdWFjMDAgXHVhZGY4XHViODI0XHVjODM4IFx1Yzc4OFx1YjI5NCBcdWNlNzRcdWI0ZGNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViNGE0XHVjOWQxXHViMjk0IFx1YzVmMFx1YzBiMFx1Yzc1OCBcdWNkNWNcdWMxOGMgXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxNjkyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRUVQUk9NIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBhbmQgU3RhbmtvIGVhY2ggaGF2ZSBvbmUgRUVQUk9NIHJlY3Rhbmd1bGFyIG1lbW9yeSBtb2R1bGUgY29uc2lzdGluZyBvZiBSJnRpbWVzOzE2IGJpdHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZXkgYWxzbyBoYXZlIHRoZSBjaXJjdWl0cnkgbmVlZGVkIHRvIHdyaXRlIGRhdGEgaW50byB0aGUgbWVtb3J5IG1vZHVsZS4gSW4gb25lIG9wZXJhdGlvbiB0aGV5IGNhbiBjaGFuZ2UgdGhlIHN0YXRlIG9mIGEgY29udGlndW91cyBzZXF1ZW5jZSBvZiBiaXRzIGluIGEgcm93IG9yIGNvbHVtbi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TWlya28gYW5kIFN0YW5rbyYjMzk7cyBkYWQgYXNrZWQgdGhlbSB0byB3cml0ZSBhIHBhcnRpY3VsYXIgYXJyYW5nZW1lbnQgb2YgYml0cyBpbnRvIHRoZWlyIG1lbW9yeSBtb2R1bGVzLiBXaG9ldmVyIGlzIGZhc3RlciB3aWxsIGdldCByZXBlYXRzIGZvciBsdW5jaCBzbyBNaXJrbyBpcyBsb29raW5nIGZvciBhIHByb2dyYW0gd2hpY2ggd2lsbCBoZWxwIGhpbSB3aW4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB3aGljaCB3aWxsIGRldGVybWluZSB0aGUgc21hbGxlc3QgcG9zc2libGUgbnVtYmVyIG9mIG9wZXJhdGlvbnMgbmVlZGVkIGZvciBNaXJrbyB0byB3cml0ZSB0aGUgZ2l2ZW4gZGF0YSBpbnRvIGhpcyBtZW1vcnkgbW9kdWxlLiBJbml0aWFsbHksIGFsbCBiaXRzIGluIHRoZSBtZW1vcnkgbW9kdWxlIGFyZSB6ZXJvLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYW4gaW50ZWdlciBSICgxICZsZTsgUiAmbGU7IDUwKSwgdGhlIG51bWJlciBvZiByb3dzIGluIHRoZSBtb2R1bGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBSIHJvd3MgY29udGFpbnMgYSBzdHJpbmcgb2YgMTYgZGlnaXRzICYjMzk7MCYjMzk7IG9yICYjMzk7MSYjMzk7LCBkYXRhIHRvIGJlIHdyaXR0ZW4gaW50byB0aGUgbW9kdWxlLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgc21hbGxlc3QgbnVtYmVyIG9mIG9wZXJhdGlvbnMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==