1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.StringTokenizer;


public class kug {

	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))){
			loadData(br);
			System.out.println(solveProblem());
		} catch (Exception e) {
			e.printStackTrace();
		} finally {
			System.exit(0);
		}
		
	}
	private static int n;
	private static List<Cost> costs;
	
	private static void loadData(BufferedReader br) throws IOException{
		n = Integer.parseInt(br.readLine());
		costs = new ArrayList<kug.Cost>(((1+n)*n)/2);
		
		for (int i = 0; i < n; i++){
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = i; j < n; j++){
				int cost = Integer.parseInt(st.nextToken());
				costs.add(new Cost(cost, i, j));
			}
		}
		
		costs.sort((c1,c2) -> Integer.compare(c1.cost, c2.cost));
	}
	
	static boolean[][] visited;
	
	private static long solveProblem() {
		visited = new boolean[n][n];
		
		long result = 0;
		int count = n;
		Iterator<Cost> it = costs.iterator();
		while(count > 0){
			Cost cost = it.next();
			if (add(cost.i, cost.j)){
//				System.out.println("[" + cost.i + ", " + cost.j + "]");
				result += cost.cost;
				count--;
			}
		}
		
		return result;
	}
	
	
	
	private static boolean add(int i, int j) {
		if (visited[i][j])
			return false;
		
		visited[i][j] = true;
		
		for (int j2 = i + 1; j2 < j; j2++)
			if (visited[i][j2])
				add(j2+1, j);
		
		for (int j2 = j + 1; j2 < n; j2++)
			if (visited[i][j2])
				add(j+1, j2);
		
		for (int j2 = j + 1; j2 < n; j2++)
			if (visited[j+1][j2])
				add(i,j2);
		
		for (int i2 = 0; i2 < i; i2++)
			if (visited[i2][j])
				add(i2, i-1);
		
		for (int i2 = i+1; i2 < j; i2++)
			if (visited[i2][j])
				add(i, i2-1);
		
		for (int i2 = 0; i2 < i; i2++)
			if (visited[i2][i-1])
				add(i2, j);
		
		return true;
	}



	static class Cost implements Comparable<Cost> {

		final int cost;
		final int i,j;

		Cost(int cost, int i, int j) {
			super();
			this.cost = cost;
			this.i = i;
			this.j = j;
		}

		@Override
		public int compareTo(Cost o) {
			return Integer.compare(cost, o.cost);
		}

		@Override
		public String toString() {
			return "Cost [cost=" + cost + ", i=" + i + ", j=" + j + "]";
		}
		
	}
	
}