1 /**************************************************************  2     Problem: 2055  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:536 ms  7     Memory:8624 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <algorithm> 12   13 using namespace std; 14 const int inf = (int) 1e9; 15 const int N = 205; 16 const int M = 500005; 17   18 struct edges{ 19     int next, to, f, cost; 20     edges() {} 21     edges(int _next, int _to, int _f, int _cost) : next(_next), to(_to), f(_f), cost(_cost) {} 22 } e[M]; 23    24 int n, m, tot = 1; 25 int first[N], Del[N], d[N], g[N]; 26 bool v[N]; 27 int q[N], l, r; 28 int S, S1, T; 29   30 inline int read() { 31     int x = 0, sgn = 1; 32     char ch = getchar(); 33     while (ch < ‘0‘ || ‘9‘ < ch) { 34         if (ch == ‘-‘) sgn = -1; 35         ch = getchar(); 36     } 37     while (‘0‘ <= ch && ch <= ‘9‘) { 38         x = x * 10 + ch - ‘0‘; 39         ch = getchar(); 40     } 41     return sgn * x; 42 } 43   44 inline void add_edge(int x, int y, int f, int c) { 45     e[++tot] = edges(first[x], y, f, c); 46     first[x] = tot; 47 } 48    49 void Add_Edges(int x, int y, int f, int c) { 50     add_edge(x, y, f, c); 51     add_edge(y, x, 0, -c); 52 } 53    54 inline int calc() { 55     int flow = inf, x; 56     for (x = g[T]; x; x = g[e[x ^ 1].to]) 57         flow = min(flow, e[x].f); 58     for (x = g[T]; x; x = g[e[x ^ 1].to]) 59         e[x].f -= flow, e[x ^ 1].f += flow; 60     return flow; 61 } 62    63 bool spfa() { 64     int x, y; 65     for (x = 1; x <= T; ++x) 66         d[x] = inf; 67     d[S] = 0, v[S] = 1, q[0] = S; 68     for(l = r = 0; l != (r + 1) % N; ++l %= N) { 69         for (x = first[q[l]]; x; x = e[x].next) 70             if (d[q[l]] + e[x].cost < d[y = e[x].to] && e[x].f) { 71                 d[y] = d[q[l]] + e[x].cost; 72                 g[y] = x; 73                 if (!v[y]) 74                     q[++r %= N] = y, v[y] = 1; 75             } 76         v[q[l]] = 0; 77     } 78     return d[T] != inf; 79 } 80   81 inline int work() { 82     int res = 0; 83     while (spfa()) 84         res += calc() * d[T]; 85     return res; 86 } 87   88 int main() { 89     int i, j, x; 90     n = read(), m = read(); 91     S = n * 2 + 1, S1 = n * 2 + 2, T = n * 2 + 3; 92     for (i = 1; i <= n; ++i) { 93         x = read(); 94         Add_Edges(i, i + n, 0, 0); 95         Del[i] -= x, Del[i + n] += x; 96     } 97     Add_Edges(S, S1, m, 0); 98     for (i = 1; i <= n; ++i) 99         Add_Edges(S1 ,i, inf, 0);100     for (i = 1; i <= n; ++i)101         for (j = i + 1; j <= n; ++j)102             if ((x = read()) != -1)103                 Add_Edges(i + n, j, inf, x);104     for (i = 1; i <= n * 2; ++i)105         if (Del[i] > 0) Add_Edges(S, i, Del[i], 0);106         else Add_Edges(i, T, -Del[i], 0);107     printf("%d\n", work());108     return 0;109 }