input

1
5
1 2 4 0 
3 0 3 2 
2 3 2 0 
4 2 0 3 
3 3 2 1 

output

9

input

1
4
0 4 1 1 
3 0 3 2 
0 2 4 1 
0 3 0 4 

output

8