#include<bits/stdc++.h>

using namespace std;

#define il inline

#define gc getchar()

#define t(i) edge[i].to

#define w(i) edge[i].wei

#define n(i) edge[i].nxt

#define ri register int

#define rb register int

#define rc register char

#define rp(i,x,y) for(ri i=x;i<=y;++i)

#define my(i,x,y) for(ri i=x;i>=y;--i)

#define e(i,x) for(ri i=head[x];~i;i=n(i))

const int N=+,M=+,inf=1e8;

int n,m,dep[N],head[N],cur[N],S,T,ed_cnt=-,as;

bool vis[N];

struct ed{int to,nxt,wei;}edge[N<<];

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

il int nam(ri l,ri r){return (l-)*n+r+;}

il void ad(ri x,ri y,ri z)

{edge[++ed_cnt]=(ed){x,head[y],z};head[y]=ed_cnt;edge[++ed_cnt]=(ed){y,head[x],};head[x]=ed_cnt;}

il bool bfs()

{

    queue<int>Q;Q.push(S);memset(dep,,sizeof(dep));dep[S]=;

    while(!Q.empty())

    {

        ri nw=Q.front();Q.pop();

        e(i,nw)if(w(i) && !dep[t(i)]){dep[t(i)]=dep[nw]+,Q.push(t(i));if(t(i)==T)return ;}

    }

    return ;

}

il int dfs(ri nw,ri flow)

{

    if(nw==T || !flow)return flow;ri ret=;

    for(ri &i=cur[nw];~i;i=n(i))

        if(w(i) && dep[t(i)]==dep[nw]+)

        {ri tmp=dfs(t(i),min(flow,w(i)));ret+=tmp,w(i)-=tmp;w(i^)+=tmp,flow-=tmp;}

    return ret;

}

il int dinic(){ri ret=;while(bfs()){rp(i,S,T)cur[i]=head[i];while(int d=dfs(S,inf))ret+=d;}return ret;}

int main()

{

    //freopen("3749.in","r",stdin);freopen("3749.out","w",stdout);

    n=read();m=read();S=;T=n*n++;memset(head,-,sizeof(head));

    rp(i,,n){ri tmp=read(),id=nam(i,i);if(!vis[tmp])ad(T,tmp,m*tmp*tmp),vis[tmp]=;ad(tmp,id,inf);ad(T,id,tmp);}

    rp(i,,n)

        rp(j,i,n)

        {

            ri tmp=read(),id1=nam(i,j),id2=nam(i,j-),id3=nam(i+,j);

            if(i!=j)ad(id2,id1,inf),ad(id3,id1,inf);

            if(tmp>)ad(id1,S,tmp),as+=tmp;else ad(T,id1,-tmp);

        }

//    printf("as=%d\n",as);

    printf("%d\n",as-dinic());

    return ;

}