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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeMap;


public class kug {

	public static class CostRange implements Comparable<CostRange> {
		
		private int cost;
		private int i;
		private int j;

		public CostRange(int cost, int i, int j) {
			this.cost = cost;
			this.i = i;
			this.j = j;
		}

		public int getCost() {
			return cost;
		}
		
		public int getI() {
			return i;
		}
		
		public int getJ() {
			return j;
		}
		
		@Override
		public int compareTo(CostRange cr) {
			return Integer.compare(this.cost, cr.cost);
		}

		@Override
		public String toString() {
			return "[c=" + cost + ",i=" + i + ",j=" + j + "]";
		}		
				
	}
	
	public static void main(String[] args) {
		try{
			BufferedReader buffReader = new BufferedReader(new InputStreamReader(System.in));
			int n = Integer.parseInt(buffReader.readLine());
			int costTable[][] = new int[n][];
			int redundancyTable[][] = new int[n][];
			boolean redundancyTestTable[][] = new boolean[n][];
			CostRange costRangeTable[] = new CostRange[(n+1)*n/2];
			int costRangeTableIndex = 0;
			for(int i=0; i<n; i++){
				costTable[i] = new int[n-i];
				redundancyTable[i] = new int[n-i];
				redundancyTestTable[i] = new boolean[n-i];
				StringTokenizer tokenizer = new StringTokenizer(buffReader.readLine());
				for(int j=0; j<n-i; j++){
					costTable[i][j] = Integer.parseInt(tokenizer.nextToken());
					redundancyTable[i][j] = 0;
					redundancyTestTable[i][j] = true;
					costRangeTable[costRangeTableIndex++] = new CostRange(costTable[i][j],i,j);
				}

			}
			Arrays.sort(costRangeTable);
			ArrayList<CostRange> costList = new ArrayList<CostRange>(n);

			TreeMap<Integer, Integer> redundancyRangeMap = new TreeMap<Integer, Integer>();
			for(CostRange cr : costRangeTable){
				if(redundancyTestTable[cr.getI()][cr.getJ()] && (redundancyTable[0][cr.getI()+cr.getJ()] - redundancyTable[0][Math.max(0,cr.getI()+cr.getJ()-1)] <= 1)){
					costList.add(cr);
					for(int j = cr.getJ(); j<n; j++){
						for(int i=Math.max(0,cr.getI()+cr.getJ()-j); i<Math.min(cr.getI()+1,n-j); i++){
							redundancyTable[i][j]++;
							if(redundancyTable[i][j] == j+1)
								redundancyRangeMap.put(i, j);
						}
					}
					while(!redundancyRangeMap.isEmpty()){
						Map.Entry<Integer, Integer> rangeEntry = redundancyRangeMap.pollFirstEntry();
						if(redundancyTestTable[rangeEntry.getKey()][rangeEntry.getValue()]){
							for(int i=rangeEntry.getKey(); i<=rangeEntry.getKey()+rangeEntry.getValue()+1; i++){
								int j = rangeEntry.getValue()+rangeEntry.getKey()-i;
								while(j >= 0 && redundancyTestTable[i][j]){
									redundancyTestTable[i][j] = false;
									j--;
								}
							}
						}
					}
				}
			}
			long minCost = 0;
			for(CostRange cr : costList)
				minCost += cr.getCost();
			
			System.out.println(minCost);
			
		}catch(Exception e){
			e.printStackTrace();
		}

	}

}