시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 76 18 13 32.500%

문제

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
W3sicHJvYmxlbV9pZCI6IjE2MDkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNjMjhcdWM3NTggXHVhY2Y1XHVhY2E5IiwiZGVzY3JpcHRpb24iOiI8cD5OJnRpbWVzO04gXHVhY2E5XHVjNzkwXHVjNzU4IFx1YWMwMSBcdWNlNzhcdWM1ZDAgXHVjMjE4XHVhYzAwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4MDFcdWQ2MDAgXHVjNzg4XHViMjk0IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWJhYThcdWM1OTFcdWM3NTggXHVhYzhjXHVjNzg0IFx1YmNmNFx1YjRkY1x1YWMwMCBcdWM3ODhcdWIyZTQuIFx1ZDNiOFx1Yzc1OFx1YzBjMSBcdWFjMDBcdWM3YTUgXHVjNjdjXHVjYWJkIFx1YzcwNCBcdWNlNzhcdWM3NTggXHVjODhjXHVkNDVjXHViOTdjICgxLCAxKSwgXHVhYzAwXHVjN2E1IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM1NDRcdWI3OTggXHVjZTc4XHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1Yjk3YyAoTiwgTilcdWM3M2NcdWI4NWMgXHVjMGRkXHVhYzAxXHVkNTVjXHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCBcdWM1ZjQgXHViYzg4XHVkNjM4LCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCBcdWQ1ODkgXHViYzg4XHVkNjM4XHViOTdjIFx1YWMwMVx1YWMwMSBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIFx1Yzc3NCBcdWFjOGNcdWM3ODQgXHViY2Y0XHViNGRjXHVjNWQwXHVjMTFjIFx1Yzc4NFx1Yzc1OFx1Yjg1YyBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1Y2U3OFx1Yzc0NCBcdWFjZThcdWI3N2MgXHVjYzI4KFx1OGVjYSlcdWI5N2MgXHVkNTU4XHViMDk4XHVjNTI5IFx1YjE5M1x1YzczY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YmIzY1x1Yjg2MCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1Y2U3OFx1Yzc0MCBcdWMxMWNcdWI4NWMgXHViMmVjXHViNzdjXHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzkwXHVjMmUwXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWM1ZjQgXHViNjEwXHViMjk0IFx1YWMxOVx1Yzc0MCBcdWQ1ODlcdWM1ZDAgXHVjYzI4KFx1OGVjYSlcdWFjMDAgXHVkNTU4XHViMDk4XHViNzdjXHViM2M0IFx1YjE5M1x1YzVlYyBcdWM3ODhcdWIyZTRcdWJhNzQgXHVhZGY4IFx1Y2U3OFx1Yzc0MCAmcXVvdDtcdWNjMjhcdWM3NTggXHVhY2Y1XHVhY2E5XHVjNzQ0IFx1YmMxYlx1YjI5NCBcdWNlNzgmcXVvdDtcdWM1ZDAgXHVkNTc0XHViMmY5XHViNDFjXHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MgXHVjYzI4KFx1OGVjYSlcdWFjMDAgXHVjOWMxXHVjODExIFx1YjE5M1x1YzVlYyBcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNzQwICZxdW90O1x1Y2MyOFx1Yzc1OCBcdWFjZjVcdWFjYTlcdWM3NDQgXHViYzFiXHViMjk0IFx1Y2U3OCZxdW90O1x1YzVkMCBcdWQ1NzRcdWIyZjlcdWI0MThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjOGNcdWM3ODQgXHViY2Y0XHViNGRjXHVjNWQwIFx1YzgwMVx1ZDYwMCBcdWM3ODhcdWIyOTQgXHVjMjE4XHViNGU0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YmE3NCwgJnF1b3Q7XHVjYzI4XHVjNzU4IFx1YWNmNVx1YWNhOVx1Yzc0NCBcdWJjMWJcdWIyOTQgXHVjZTc4JnF1b3Q7XHVjNWQwIFx1YzgwMVx1ZDYwMCBcdWM3ODhcdWIyOTQgXHVjMjE4XHViNGU0XHVjNzU4IFx1ZDU2OVx1Yzc3NCBcdWNkNWNcdWIzMDBcdWFjMDAgXHViNDE4XHViM2M0XHViODVkIFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVjYzI4KFx1OGVjYSlcdWI5N2MgXHViYzMwXHVjZTU4XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE4oMiAmbGU7IE4gJmxlOyAzMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHVjNWI0XHVjMTFjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWFjOGNcdWM3ODQgXHViY2Y0XHViNGRjXHVjNWQwIFx1YzgwMVx1ZDYwMCBcdWM3ODhcdWIyOTQgXHVjMjE4XHViNGU0XHVjNzc0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgTlx1YWMxY1x1YzUyOSBcdWJlNDggXHVjZTc4XHVjNzQ0IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWI0NTBcdWFjZTAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVjMjE4XHViMjk0IFx1YmFhOFx1YjQ1MCAwIFx1Yzc3NFx1YzBjMSAxLDAwMFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCwgJnF1b3Q7XHVjYzI4XHVjNzU4IFx1YWNmNVx1YWNhOVx1Yzc0NCBcdWJjMWJcdWIyOTQgXHVjZTc4JnF1b3Q7XHVjNWQwIFx1YzgwMVx1ZDYwMCBcdWM3ODhcdWIyOTQgXHVjMjE4XHViNGU0XHVjNzU4IFx1ZDU2OVx1Yzc3NCBcdWNkNWNcdWIzMDBcdWFjMDAgXHViNDE4XHViM2M0XHViODVkIFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVjYzI4KFx1OGVjYSlcdWI5N2MgXHViYzMwXHVjZTU4XHVkNTg4XHVjNzQ0IFx1YjU0YyBcdWFkZjggXHVjZDVjXHViMzAwXHVkNTY5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxNjA5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoia3VsZSIsImRlc2NyaXB0aW9uIjoiPHA+VHdvIHJvb2tzIGFyZSB0byBiZSBwbGFjZWQgb24gYSBjaGVzcy1saWtlIE54TiBnYW1lIGJvYXJkLiBFYWNoIHNxdWFyZSBjb250YWlucyBhIHNpbmdsZSBub25uZWdhdGl2ZSBpbnRlZ2VyLiBUaGUgcm9va3MgbXVzdCBiZSBwbGFjZWQgb24gZGlmZmVyZW50IHNxdWFyZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldlIHNheSB0aGF0IHNvbWUgc3F1YXJlIG9uIHRoZSBib2FyZCBpcyBhdHRhY2tlZCBpZiB0aGF0IHNxdWFyZSBpcyBpbiB0aGUgc2FtZSByb3cgb3IgaW4gdGhlIHNhbWUgY29sdW1uIGFzIG9uZSBvZiB0aGUgcm9va3MuIFNxdWFyZXMgY29udGFpbmluZyB0aGUgcm9va3MgdGhlbXNlbHZlcyBhcmUgbm90IGNvbnNpZGVyZWQgYXR0YWNrZWQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldlIHdhbnQgdG8gcGxhY2Ugb3VyIHJvb2tzIHNvIHRoYXQgdGhlIHRvdGFsIHN1bSBvZiB0aGUgbnVtYmVycyBvbiBhbGwgYXR0YWNrZWQgc3F1YXJlcyBpcyBhcyBsYXJnZSBhcyBwb3NzaWJsZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBmaW5kIHRoaXMgbWF4aW11bSBzdW0uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhbiBpbnRlZ2VyIE4sIDIgJmxlOyBOICZsZTsgMzAwLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyBOIGludGVnZXJzLiBFYWNoIG51bWJlciB3aWxsIGJlIGdyZWF0ZXIgdGhhbiBvciBlcXVhbCB0byAwIGFuZCBsZXNzIHRoYW4gb3IgZXF1YWwgdG8gMTAwMC4gVGhlc2UgYXJlIHRoZSBudW1iZXJzIG9uIHRoZSBib2FyZC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gYSBzaW5nbGUgaW50ZWdlciAmbmRhc2g7IHRoZSBtYXhpbXVtIHN1bSBmcm9tIHRoZSB0YXNrIGRlc2NyaXB0aW9uLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=