PO-보관

각 대회가 끝난 뒤, 프로그래밍 올림피아드는 참가자들의 풀이를 영구히 보관한다. 하지만 대회 중 제출되는 풀이 대부분은 상당히 비슷하다. 버그를 수정하는 참가자는 풀이에서 단 한 줄만 변경할 수도 있다. 이러한 경우에는 원래 풀이와 변경된 풀이를 둘 다 저장할 필요가 없다. 대신 두 풀이 중 하나와 두 풀이 사이에 이루어진 변경 사항을 저장할 수 있다. 이 작업은 여러 단계로도 수행할 수 있다. 즉, 풀이 $A$을 저장한 다음 $A$와 다른 풀이 $B$ 사이의 변경 사항을 저장하고, 마지막으로 $B$와 세 번째 풀이 $C$ 사이의 변경 사항을 저장할 수 있다.

한 대회에서 총 $N$개의 풀이가 제출되었으며, 그 크기는 $S[0], S[1], \dots, S[N-1]$바이트이다. $i$번째 풀이가 저장되어 있거나 복원될 수 있다면, 크기가 $D[i][j]$바이트인 변경 사항을 저장하여 $j$번째 풀이를 복원할 수 있다.

대부분의 테스트 케이스 그룹에서는 차이의 크기가 대칭이다. 즉, $D[i][j] = D[j][i]$이다(일반적인 Unix-diff 파일과 마찬가지이다). 하지만 마지막 그룹에서는 이 조건이 성립하지 않아도 되는 더 일반적인 차이를 고려한다. 예를 들어 문자열 abaabbaaa와 aaaaaa 사이의 차이를 한 방향에서는 모든 `b` 삭제''로 저장하고, 다른 방향에서는 위치 2, 5, 6에 b 삽입''으로 저장할 수 있다고 생각해 보자. 이때 후자의 변경 사항은 전자보다 저장하는 데 더 많은 공간이 필요하다.

모든 풀이를 복원할 수 있도록 저장해야 하는 데이터의 최소량은 몇 바이트인가?

채점

여러 테스트 케이스 그룹으로 풀이를 테스트한다. 한 그룹에서 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

1 | 11 | 모든 수 $D[i][j]$는 ($i = j$인 경우를 제외하면) 동일하다

2 | 27 | 모든 수 $S[i]$는 동일하며, $D[i][j] = D[j][i]$

3 | 48 | $D[i][j] = D[j][i]$

4 | 14 | 제한 없음

첫 번째 줄에 정수 $1 \le N \le 100$이 주어진다. 다음 줄에 $N$개의 정수 $1 \le S[0], S[1], \dots, S[N-1] \le 1\,000\,000$가 주어진다. 다음 $N$개의 줄에는 각각 $N$개의 정수가 주어진다. 이 줄들 중 $i$번째 줄에는 수 $1 \le D[i][0], D[i][1], \dots, D[i][N-1] \le 1\,000\,000$가 주어진다. 모든 $i$에 대해 $D[i][i] = 0$이다.

저장해야 하는 데이터의 최소량을 바이트 단위의 수 하나로 출력한다.