#include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<queue>

 using namespace std;

 const int maxn=;

 const int minf=;

 int n,m,S,T,SS,mx,ans;

 struct nod{

     int x,y,v,co,rev,next;

 }e[maxn*maxn];

 int head[maxn]={},tot=;

 int dis[maxn]={},fa[maxn]={},vis[maxn]={};

 inline void init(int x,int y,int v,int co){

     e[++tot].x=x;e[tot].y=y;e[tot].v=v;e[tot].co=co;e[tot].rev=tot+;e[tot].next=head[x];head[x]=tot;

     e[++tot].x=y;e[tot].y=x;e[tot].v=;e[tot].co=-co;e[tot].rev=tot-;e[tot].next=head[y];head[y]=tot;

 }

 queue<int>q;

 inline bool SPFA(){

     memset(dis,,sizeof(dis));

     memset(fa,,sizeof(fa));

     mx=dis[];

     q.push(S);dis[S]=;

     while(!q.empty()){

         int x=q.front();q.pop();vis[x]=;

         for(int i=head[x];i;i=e[i].next){

             int y=e[i].y;

             if((!e[i].v)||dis[y]<=e[i].co+dis[x])continue;

             dis[y]=e[i].co+dis[x];fa[y]=i;

             if(!vis[y]){

                 q.push(y);vis[y]=;

             }

         }

     }

     return dis[T]!=mx;

 }

 inline void doit(){

     int val=mx;

     for(int i=fa[T];i;i=fa[e[i].x])val=min(val,e[i].v);

     for(int i=fa[T];i;i=fa[e[i].x]){e[i].v-=val; e[e[i].rev].v+=val; ans+=e[i].co*val;}

 }

 int main(){

     int x;

     scanf("%d%d",&n,&m);S=n*+;T=S+;SS=T+;

     for(int i=;i<=n;i++){

         scanf("%d",&x);

         if(x<=)continue;

         init(i,i+n,,);

         init(S,i+n,x,); init(i,T,x,);

     }

     for(int i=;i<=n;i++){

         for(int j=i+;j<=n;j++){

             scanf("%d",&x);if(x!=-)init(i+n,j,minf,x);

         }

     }

     init(S,SS,m,);

     for(int i=;i<=n;i++) init(SS,i,minf,);

     ans=;

     while(SPFA())doit();

     printf("%d\n",ans);

     return ;

 }