PO Archiving

Time limit1sMemory limit1024 MB

Summary

Choose a set of solutions to store and directed diffs to save so every solution is reconstructable, minimizing total bytes.

Level: Medium7 of 10
Topics: Graph, Minimum spanning tree, Greedy, Implementation
Solved: No attempts yet

Problem

After every competition, the Programming Olympiad archives the participants' solutions forever. Most of the solutions submitted during a competition are quite similar, though. A contestant who fixes a bug might only change a single line in a solution. In these cases it is unnecessary to save both the original solution and the changed solution. Instead we can save one of the solutions along with the changes that were made between the two solutions. This can also happen in several steps, so that one saves a solution $A$ , then saves the changes between $A$ and another solution $B$ , and finally the changes between $B$ and a third solution $C$ .

In total $N$ solutions were submitted during a competition, with sizes $S[0], S[1], \dots, S[N-1]$ bytes. If the $i$ -th solution is either saved or can be reconstructed, then the $j$ -th solution can be reconstructed if the changes that are $D[i][j]$ bytes large are saved.

In most test case groups the diff sizes will be symmetric, i.e. $D[i][j] = D[j][i]$ (similar to ordinary Unix diff files). For the last group, however, we consider more general diffs where this need not hold. For example, we can imagine that the difference between the strings abaabbaaa and aaaaaa is saved as "remove all b" in one direction, and "insert b at positions 2, 5, 6" in the other, where the latter change requires more space to save than the former.

What is the minimum amount of data (in bytes) that must be saved in order for all solutions to be reconstructable?

Input

The first line contains the integer $1 \le N \le 100$ . The next line contains the $N$ integers $1 \le S[0], S[1], \dots, S[N-1] \le 1\,000\,000$ . The next $N$ lines each contain $N$ integers. The $i$ -th of these lines contains the numbers $1 \le D[i][0], D[i][1], \dots, D[i][N-1] \le 1\,000\,000$ . $D[i][i] = 0$ for all $i$ .

Output

Print a single number: the minimum amount of data that must be saved, in bytes.

Examples2

Example 1
Input
```
3
20 10 30
0 35 15
35 0 45
15 45 0
```
Expected output
```
45
```
Example 2
Input
```
3
100 101 102
0 5 2
30 0 1
40 50 0
```
Expected output
```
106
```