최대이익 계산하기

가로,세로의 크기가 N*N인 이익이 있다.

이익을 얻을 때는 가로 혹은 세로 절반으로 나누어 한쪽 절반에 해당하는 부분을 모두 활용하여 얻는다.

특정부분을 모두 활용하여 개발할 때 얻을 수 있는 이익은, 해당 부분에서 얻을 수 있는 이익 중 최댓값이다.

예를들어

0 2 3 4

5 1 8 8

3 2 9 4

4 1 7 5 이면

0 2 3 4

5 1 8 8

0 2

5 1

3 2

4 1

3 4

8 8

9 4

7 5

3 2 9 4

4 1 7 5

이렇게 4가지 선택지가 있다.

각각의 선택지에 대하여 얻을 수 있는 이익은, 해당 면적에서 얻을 수 있는 이익의 최댓값으로, 이는 순서대로

8,5,9,9 이다.

이렇게 이익을 얻고나면, 해당면적은 더이상 이익을 얻을 수 없고 남은 면적을 반복하여 이익을 얻는다.

예를들어 처음에 왼쪽 절반에서 이익을 얻었다면, 오른쪽 절반을 상/하/좌/우로 나누어 이익을 얻어야한다.

맨 마지막에는 결국 두 개의 칸이 남게된다.

그 두개의 칸을 또 절반으로 나누어 한 개의 칸에서 이익을 얻으면, 마지막 최종적으로 하나의 칸이 남게된다. 이와 같이 남은 칸이 1개일 경우에는 해당 칸에서 이익을 얻을 수 없어 이익얻기를 종료한다.

위 규칙을 토대로 예시의 이익을 모두 얻었을 때 최대 30만큼의 이익을 얻을 수 있다.

입력

첫 번째 줄에 N을 입력받는다.

N=2,4,8,16,32 중 하나

이후 N 개의 줄에 대하여 공백을 구분자로 얻을 수 있는 이익을 입력받는다. (모두 양의 정수이다)

1<=얻을 수 있는 이익<=100,000

출력

얻을 수 있는 이익의 합 중 최댓값을 출력한다.

이익의 합<=1,000,000

입력 예시

4

0 2 3 4

5 1 8 8

3 2 9 4

4 1 7 5

출력 예시

30

제가 짠 것은 아래코드인데

계속 이상하게 돌더라구요 ㅠㅠ 규칙을 잘못찾는건지...

혹시 row와 col을 어떻게 돌려야할 지 알려주실 수 있나요?