시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 39 12 7 31.818%

문제

N×N 격자의 각 칸에 수가 하나씩 적혀 있는 정사각형 모양의 게임 보드가 있다. 편의상 가장 왼쪽 위 칸의 좌표를 (1, 1), 가장 오른쪽 아래 칸의 좌표를 (N, N)으로 생각한다. 첫 번째 좌표는 열 번호, 두 번째 좌표는 행 번호를 각각 나타낸다. 이 게임 보드에서 임의로 두 개의 칸을 골라 차(車)를 하나씩 놓으려고 한다. 물론 두 개의 칸은 서로 달라야 한다.

자신과 같은 열 또는 같은 행에 차(車)가 하나라도 놓여 있다면 그 칸은 "차의 공격을 받는 칸"에 해당된다. 하지만 차(車)가 직접 놓여 있는 칸은 "차의 공격을 받는 칸"에 해당되지 않는다.

게임 보드에 적혀 있는 수들이 주어지면, "차의 공격을 받는 칸"에 적혀 있는 수들의 합이 최대가 되도록 두 개의 차(車)를 배치하는 프로그램을 작성하시오.

입력

첫째 줄에 N(2≤N≤300)이 주어진다. 이어서 N개의 줄에 걸쳐 게임 보드에 적혀 있는 수들이 한 줄에 N개씩 빈 칸을 사이에 두고 주어진다. 주어지는 수는 모두 0 이상 1,000이하의 정수이다.

출력

첫째 줄에, "차의 공격을 받는 칸"에 적혀 있는 수들의 합이 최대가 되도록 두 개의 차(車)를 배치했을 때 그 최대합을 출력한다.

예제 입력 1

3
0 1 4
3 0 2
1 4 1

예제 출력 1

15
W3sicHJvYmxlbV9pZCI6IjE2MDkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNjMjhcdWM3NTggXHVhY2Y1XHVhY2E5IiwiZGVzY3JpcHRpb24iOiI8cD5OJnRpbWVzO04gXHVhY2E5XHVjNzkwXHVjNzU4IFx1YWMwMSBcdWNlNzhcdWM1ZDAgXHVjMjE4XHVhYzAwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4MDFcdWQ2MDAgXHVjNzg4XHViMjk0IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWJhYThcdWM1OTFcdWM3NTggXHVhYzhjXHVjNzg0IFx1YmNmNFx1YjRkY1x1YWMwMCBcdWM3ODhcdWIyZTQuIFx1ZDNiOFx1Yzc1OFx1YzBjMSBcdWFjMDBcdWM3YTUgXHVjNjdjXHVjYWJkIFx1YzcwNCBcdWNlNzhcdWM3NTggXHVjODhjXHVkNDVjXHViOTdjICgxLCAxKSwgXHVhYzAwXHVjN2E1IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM1NDRcdWI3OTggXHVjZTc4XHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1Yjk3YyAoTiwgTilcdWM3M2NcdWI4NWMgXHVjMGRkXHVhYzAxXHVkNTVjXHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCBcdWM1ZjQgXHViYzg4XHVkNjM4LCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCBcdWQ1ODkgXHViYzg4XHVkNjM4XHViOTdjIFx1YWMwMVx1YWMwMSBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIFx1Yzc3NCBcdWFjOGNcdWM3ODQgXHViY2Y0XHViNGRjXHVjNWQwXHVjMTFjIFx1Yzc4NFx1Yzc1OFx1Yjg1YyBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1Y2U3OFx1Yzc0NCBcdWFjZThcdWI3N2MgXHVjYzI4KFx1OGVjYSlcdWI5N2MgXHVkNTU4XHViMDk4XHVjNTI5IFx1YjE5M1x1YzczY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YmIzY1x1Yjg2MCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1Y2U3OFx1Yzc0MCBcdWMxMWNcdWI4NWMgXHViMmVjXHViNzdjXHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG48cD5cdWM3OTBcdWMyZTBcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YzVmNCBcdWI2MTBcdWIyOTQgXHVhYzE5XHVjNzQwIFx1ZDU4OVx1YzVkMCBcdWNjMjgoXHU4ZWNhKVx1YWMwMCBcdWQ1NThcdWIwOThcdWI3N2NcdWIzYzQgXHViMTkzXHVjNWVjIFx1Yzc4OFx1YjJlNFx1YmE3NCBcdWFkZjggXHVjZTc4XHVjNzQwICZxdW90O1x1Y2MyOFx1Yzc1OCBcdWFjZjVcdWFjYTlcdWM3NDQgXHViYzFiXHViMjk0IFx1Y2U3OCZxdW90O1x1YzVkMCBcdWQ1NzRcdWIyZjlcdWI0MWNcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWNjMjgoXHU4ZWNhKVx1YWMwMCBcdWM5YzFcdWM4MTEgXHViMTkzXHVjNWVjIFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWM3NDAgJnF1b3Q7XHVjYzI4XHVjNzU4IFx1YWNmNVx1YWNhOVx1Yzc0NCBcdWJjMWJcdWIyOTQgXHVjZTc4JnF1b3Q7XHVjNWQwIFx1ZDU3NFx1YjJmOVx1YjQxOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuPHA+XHVhYzhjXHVjNzg0IFx1YmNmNFx1YjRkY1x1YzVkMCBcdWM4MDFcdWQ2MDAgXHVjNzg4XHViMjk0IFx1YzIxOFx1YjRlNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzQsICZxdW90O1x1Y2MyOFx1Yzc1OCBcdWFjZjVcdWFjYTlcdWM3NDQgXHViYzFiXHViMjk0IFx1Y2U3OCZxdW90O1x1YzVkMCBcdWM4MDFcdWQ2MDAgXHVjNzg4XHViMjk0IFx1YzIxOFx1YjRlNFx1Yzc1OCBcdWQ1NjlcdWM3NzQgXHVjZDVjXHViMzAwXHVhYzAwIFx1YjQxOFx1YjNjNFx1Yjg1ZCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1Y2MyOChcdThlY2EpXHViOTdjIFx1YmMzMFx1Y2U1OFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+IiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE4oMiZsZTtOJmxlOzMwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWM1YjRcdWMxMWMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YWM4Y1x1Yzc4NCBcdWJjZjRcdWI0ZGNcdWM1ZDAgXHVjODAxXHVkNjAwIFx1Yzc4OFx1YjI5NCBcdWMyMThcdWI0ZTRcdWM3NzQgXHVkNTVjIFx1YzkwNFx1YzVkMCBOXHVhYzFjXHVjNTI5IFx1YmU0OCBcdWNlNzhcdWM3NDQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjQ1MFx1YWNlMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWMyMThcdWIyOTQgXHViYWE4XHViNDUwIDAgXHVjNzc0XHVjMGMxIDEsMDAwXHVjNzc0XHVkNTU4XHVjNzU4IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAsICZxdW90O1x1Y2MyOFx1Yzc1OCBcdWFjZjVcdWFjYTlcdWM3NDQgXHViYzFiXHViMjk0IFx1Y2U3OCZxdW90O1x1YzVkMCBcdWM4MDFcdWQ2MDAgXHVjNzg4XHViMjk0IFx1YzIxOFx1YjRlNFx1Yzc1OCBcdWQ1NjlcdWM3NzQgXHVjZDVjXHViMzAwXHVhYzAwIFx1YjQxOFx1YjNjNFx1Yjg1ZCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1Y2MyOChcdThlY2EpXHViOTdjIFx1YmMzMFx1Y2U1OFx1ZDU4OFx1Yzc0NCBcdWI1NGMgXHVhZGY4IFx1Y2Q1Y1x1YjMwMFx1ZDU2OVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxNjA5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoia3VsZSIsImRlc2NyaXB0aW9uIjoiPHA+VHdvIHJvb2tzIGFyZSB0byBiZSBwbGFjZWQgb24gYSBjaGVzcy1saWtlIE54TiBnYW1lIGJvYXJkLiBFYWNoIHNxdWFyZSBjb250YWlucyBhIHNpbmdsZSBub25uZWdhdGl2ZSBpbnRlZ2VyLiBUaGUgcm9va3MgbXVzdCBiZSBwbGFjZWQgb24gZGlmZmVyZW50IHNxdWFyZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldlIHNheSB0aGF0IHNvbWUgc3F1YXJlIG9uIHRoZSBib2FyZCBpcyBhdHRhY2tlZCBpZiB0aGF0IHNxdWFyZSBpcyBpbiB0aGUgc2FtZSByb3cgb3IgaW4gdGhlIHNhbWUgY29sdW1uIGFzIG9uZSBvZiB0aGUgcm9va3MuIFNxdWFyZXMgY29udGFpbmluZyB0aGUgcm9va3MgdGhlbXNlbHZlcyBhcmUgbm90IGNvbnNpZGVyZWQgYXR0YWNrZWQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldlIHdhbnQgdG8gcGxhY2Ugb3VyIHJvb2tzIHNvIHRoYXQgdGhlIHRvdGFsIHN1bSBvZiB0aGUgbnVtYmVycyBvbiBhbGwgYXR0YWNrZWQgc3F1YXJlcyBpcyBhcyBsYXJnZSBhcyBwb3NzaWJsZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBmaW5kIHRoaXMgbWF4aW11bSBzdW0uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhbiBpbnRlZ2VyIE4sIDIgJmxlOyBOICZsZTsgMzAwLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyBOIGludGVnZXJzLiBFYWNoIG51bWJlciB3aWxsIGJlIGdyZWF0ZXIgdGhhbiBvciBlcXVhbCB0byAwIGFuZCBsZXNzIHRoYW4gb3IgZXF1YWwgdG8gMTAwMC4gVGhlc2UgYXJlIHRoZSBudW1iZXJzIG9uIHRoZSBib2FyZC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gYSBzaW5nbGUgaW50ZWdlciAmbmRhc2g7IHRoZSBtYXhpbXVtIHN1bSBmcm9tIHRoZSB0YXNrIGRlc2NyaXB0aW9uLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==