종이접기

면접 대비

시간 제한1초메모리 제한512 MB

요약

N=2^m인 N×N 격자에 적힌 정수를 반으로 접을 때마다 겹치는 칸의 값을 더한다. 한 값이 남을 때까지 반복한 뒤 그 값을 출력한다.

난이도: 쉬움10점 중 3점
유형: 배열, 수학, 구현
정답자: 아직 제출이 없습니다

문제

종이접기와 수학을 좋아하는 주성이는 종이접기와 수학을 한꺼번에 하는 놀이를 찾아냈다. $N \times N$ 크기의 색종이 각 칸에 수를 적어놓고, 색종이를 반으로 접을 때마다 겹치는 칸의 수를 더하는 것이다. 색종이를 더 접을 수 없을 때까지 이 작업을 반복하고, 마지막에 남는 수를 구한다.

아래 그림은 2×2 크기의 색종이로 이 놀이를 하는 과정을 자세히 나타낸 것이다.

색종이를 왼쪽에서 오른쪽으로 정확히 반을 접는다.
겹치는 두 칸의 수를 서로 더한다. 위 그림에서는 (1, 1)과 (1, 2)가 겹치고, (2, 1)과 (2, 2)도 겹친다.
더한 값을 색종이 위에 다시 적는다.

색종이를 아래쪽에서 위쪽으로 정확히 반을 접는다.
겹치는 두 칸의 수를 서로 더한다. 위 그림에서는 (1, 1)과 (2, 1)이 겹친다.
더한 값을 색종이 위에 다시 적는다.

색종이가 두꺼워지는 것은 고려하지 않고, 더 접을 수 없을 때까지 위 과정을 반복했을 때 마지막에 남는 수를 구하여라.

입력

첫 번째 줄에는 색종이의 가로, 세로 길이를 나타내는 정수 $N$ 이 주어진다. ( $N = 2^m$ , $1 \le m \le 10$ )

두 번째 줄부터 마지막 줄까지 $N \times N$ 크기의 색종이 정보가 주어진다. 색종이의 각 칸에는 정수 $K$ 가 적혀 있다. ( $1 \le K \le 100{,}000$ )

출력

색종이를 반으로 접으면서 겹치는 칸의 수를 더하는 과정을 반복했을 때, 마지막에 남는 수를 출력한다.

예제1

예제 1
입력
```
4
2 6 5 4
1 5 7 6
9 8 8 7
1 4 7 8
```
예상 출력
```
88
```