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
#include <cstdio>
#include <cassert>
#include <algorithm>

static long long sums[2001][2001] = {};
static long long dp[2001] = {};

inline void updateIfSmaller(long long &a, long long b) {
    if (a > b) {
        a = b;
    }
}

int readSums() {
    int n, tmp;
    long long coeffs[2001] = {};

    scanf("%d", &n);

    for (int i = 0;  i < n; ++i) {
        int m = n - i;
        for (int j = 0; j < m; ++j) {
            scanf("%d", &tmp);
            coeffs[j] = tmp;
        }

        std::sort(coeffs, coeffs + m);

        for (int j = 1; j < m; ++j) {
            coeffs[j] += coeffs[j - 1];
        }

        sums[m][0] = 0;
        for (int j = 0; j < m; ++j) {
            sums[m][j + 1] = coeffs[j];
        }
    }
    return n;
}

int f(int n) {

    dp[0] = 0;

    for (int i = 1; i <= n; ++i) {
        long long result = sums[i][i];

        for (int j = 1; j < i; ++j) {
            updateIfSmaller(result, dp[i - j] + sums[i][j]);
        }
        dp[i] = result;
    }

    return dp[n];
}


int main() {
    int n = readSums();
    long long result = f(n);

    printf("%lld\n", result);

}