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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.*;

public class kug {
    private static class Interval {
        int price;
        int left;
        int right;

        private Interval(int price, int left, int right) {
            this.price = price;
            this.left = left;
            this.right = right;
        }

        private boolean isEqualTo(Interval o) {
            return left == o.left && right == o.right;
        }

        private void xor(Interval o) {
            left = Math.min(right, o.right) + 1;
            right = Math.max(right, o.right);
        }
    }

    private static class IntervalComparator implements Comparator<Interval> {
        @Override
        public int compare(Interval o1, Interval o2) {
            return Integer.compare(o1.price, o2.price);
        }
    }



    public static void main(String[] args) throws IOException {
        long sum = 0;
        InputStream input = System.in;
        BufferedReader reader = new BufferedReader(new InputStreamReader(input));
        int n = Integer.valueOf(reader.readLine());
        Interval[] selected = new Interval[n+1];
        List<Interval> list = new ArrayList<Interval>(1 + (n * n + n) / 2);
        for (int i = 0; i < n; i++) {
            String[] numberAsString = reader.readLine().split(" ");
            for (int j = 0; j < n - i; j++) {
                int cost = Integer.valueOf(numberAsString[j]);
                list.add(new Interval(cost, i+1, j + i + 1));
            }
        }
        Collections.sort(list, new IntervalComparator());
        int selectedSize = 0;
        int index = 0;
        while (index < list.size()) {
            Interval cheapest = list.get(index);
            index ++;
            while (true) {
                Interval prev = selected[cheapest.left];
                if (prev == null) {
                    selected[cheapest.left] = cheapest;
                    selectedSize ++;
                    sum += cheapest.price;
                    break;
                } else if (!prev.isEqualTo(cheapest)) {
                    cheapest.xor(prev);
                } else {
                    break;
                }
            }
            if (selectedSize == n) {
                break;
            }
        }
        System.out.println(sum);
    }

}