문제
오늘은 멤버십 회식 날이다.
멤버십 회원들은 운영자님을 사랑하는 마음을 담아 N * N 개의 술잔에 술을 따라 두었다.
각 회원이 운영자님을 사랑하는 마음이 다르기에 술잔의 술의 양도 다양하다.
큰 운영자님과 작은 운영자님은 사이가 좋기 때문에 총 마시는 술의 양의 차이가 되도록 적게 하여 마시고 싶어 한다.
그런데 술을 마시다 보면 정신이 없기 때문에 규칙을 정해 놓았다.
N * N 개의 술잔들을 두 부분으로 나누어, 큰 운영자님은 위 쪽의 술을 마시고 작은 운영자님은 아래쪽의 술을 마시기로 하였다.
이 때 각 운영자님에게 배분된 구역이 단조 증가하는 계단 모양이 되게 하려고 한다. 즉, 주어진 술잔 들을 N * N 행렬로 볼 때 작은
운영자님이 특정 열에서 할당받는 구역의 개수는 바로 왼쪽 열에서 받은 구역의 개수보다 크거나 같아야 한다.
예를 들어, 다음 세 개의 그림 중 그림 1과 2는 올바른 배정 방법으로, 회색 지역은 작은 운영자님이 마셔야 할 술잔, 흰 부분은 큰 운영자님이 마셔야 할 술잔이다. 그러나 그림 3은 술잔을 나누는 규칙을 어기는 경우이다.
입력
첫째 줄에 N (2<=N<=20) 이 주어지고, 이어서 N * N 행렬로 각 술잔에 따라진 술의 양이 0 에서 100 사이의 정수로 주어진다.
출력
첫째 줄에 최적의 방법으로 영역을 나누었을 때, 총 마시는 술의 양의 차이의 최소값을 출력한다.
