PO 아카이빙

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

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

대부분의 테스트 케이스 그룹에서 diff 크기는 대칭이다. 즉 $D[i][j] = D[j][i]$이다(일반적인 Unix diff 파일과 비슷하다). 그러나 마지막 그룹에서는 이것이 성립하지 않을 수 있는 더 일반적인 diff를 다룬다. 예를 들어 문자열 abaabbaaa와 aaaaaa의 차이는 한 방향에서는 "모든 b를 삭제"로 저장되고, 다른 방향에서는 "위치 2, 5, 6에 b를 삽입"으로 저장된다고 생각할 수 있다. 후자의 변경은 전자보다 저장 공간을 더 많이 차지한다.

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

첫 번째 줄에는 정수 $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$이다.

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