题目链接：https://www.luogu.com.cn/problem/P4553
题目大意：
图片说明
图片说明
思路：拆点，i->i+n的流量限制为[v, v]，费用为0， .然后每个点都可以作为入点，每个点都可以作为出点。为了保证m个人，我们应再建辅助源点S。s->S流量限制为[m, m]。再由S向所有的剧情点连边。

#pragma GCC optimize(3, "Ofast", "inline")
#include<bits/stdc++.h>
#define re register
using namespace std;

const int maxn = 500 + 10;
const int maxm=1e6+10;
const int inf=1<<30;

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
char buf[1<<20],*p1=buf,*p2=buf;
inline int read() {
    int f=0,fu=1;
    char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-')
            fu=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        f=(f<<3)+(f<<1)+c-48;
        c=getchar();
    }
    return f*fu;
}

struct po {
    int to,dis,nxt,w;
} edge[maxm<<1];

struct max_folw {
    int dis[maxn];
    int vis[maxn];
    int head[maxn];
    int d[maxn];
    int n,s,t,cut=-1;
    int ans=0, fy=0;

    void init(int N, int S, int T) {
        ans=0, fy=0;
        cut=-1;
        n=N, s=S, t=T;
        memset(head, -1, sizeof(head));
        memset(d, 0, sizeof(d));
    }

    void add_edge(int from,int to,int w,int dis) {
        edge[++cut].nxt=head[from];
        edge[cut].to=to;
        edge[cut].w=w;
        edge[cut].dis=dis;
        head[from]=cut;
    }
    void add(int from,int to,int w,int dis) {
        add_edge(from,to,w,dis);
        add_edge(to,from,0,-dis);
    }

    void addlr(int from,int to,int w,int l, int r){//有限制的添边
        add(from,to,r-l,w);
        d[to]+=l, d[from]-=l;
        fy+=l*w;
    }

    bool spfa() {
        memset(vis,0,sizeof(vis));
        for(re int i=0; i<=n; i++)
            dis[i]=inf;
        dis[t]=0;
        vis[t]=1;
        deque<int> q;
        q.push_back(t);
        while(!q.empty()) {
            int u=q.front();
            vis[u]=0;
            q.pop_front();
            for(re int i=head[u]; i!=-1; i=edge[i].nxt) {
                int v=edge[i].to;
                if(edge[i^1].w>0&&dis[v]>dis[u]-edge[i].dis) {
                    dis[v]=dis[u]-edge[i].dis;
                    if(!vis[v]) {
                        vis[v]=1;
                        if(!q.empty()&&dis[v]<dis[q.front()])
                            q.push_front(v);
                        else
                            q.push_back(v);
                    }
                }
            }
        }
        return dis[s]<inf;
    }
    int dfs(int u,int low) {
        if(u==t) {
            vis[t]=1;
            return low;
        }
        int diss=0;
        vis[u]=1;
        for(re int i=head[u]; i!=-1; i=edge[i].nxt) {
            int v=edge[i].to;
            if(!vis[v]&&edge[i].w!=0&&dis[u]-edge[i].dis==dis[v]) {
                int check=dfs(v,min(edge[i].w,low));
                if(check>0) {
                    fy+=check*edge[i].dis;
                    edge[i].w-=check;
                    edge[i^1].w+=check;
                    low-=check;
                    diss+=check;
                    if(low==0)
                        break;
                }
            }
        }
        return diss;
    }
    void max_flow() {

        for(int i=0; i<=n; i++){//要求访问到所有点
            if(d[i]>0){
                add(s, i, d[i], 0);
            }
            if(d[i]<0){
                add(i, t, -d[i], 0);
            }
        }

        while(spfa()) {
            vis[t]=1;
            while(vis[t]) {
                memset(vis,0,sizeof(vis));
                ans+=dfs(s,inf);
            }
        }
    }
} flow;

int main() {

    int n, m;  scanf("%d%d", &n, &m);
    int s=0, t=2*n+1, S=2*n+2, ss=2*n+3, tt=2*n+4;
    flow.init(tt+5, ss, tt);
    int x;

    flow.addlr(s, S, 0, m, m);
    for(int i=1; i<=n; i++){
        scanf("%d", &x);
        flow.addlr(i, i+n, 0, x, x);
        flow.add(S, i, m, 0);
        flow.add(i+n, t, m, 0);
    }
    for(int i=1; i<n; i++){
        for(int j=i+1; j<=n; j++){
            scanf("%d", &x);
            if(x!=-1){
                flow.add(i+n, j, inf, x);
            }
        }
    }
    flow.add(t, s, inf, 0);
    flow.max_flow();
    printf("%d\n", flow.fy);

    return 0;
}