# include <bits/stdc++.h>
using namespace std;
int s,t,a[110],c[110][110],id[110][110],d[7010],head[7010],cur[7010],to[50010],cap[50010],flow[50010],nxt[50010],tot=1;
void addedge(int u,int v,int c)
{
	to[++tot]=v;
	cap[tot]=c;
	nxt[tot]=head[u];
	head[u]=tot;
}
void add(int u,int v,int c){addedge(u,v,c);addedge(v,u,0);}
bool bfs()
{
	queue<int> que;
	memset(d+1,0,sizeof(int)*t);
	que.push(s);d[s]=1;
	while(!que.empty())
	{
		int u=que.front();que.pop();
		for(int i=head[u];i;i=nxt[i])
		{
			int v=to[i];
			if(cap[i]>flow[i] && !d[v]) d[v]=d[u]+1,que.push(v);
		}
	}
	return d[t];
}
int dfs(int u,int minn)
{
	if(u==t || !minn) return minn;
	int ans=0,f;
	for(int &i=cur[u];i;i=nxt[i])
	{
		int v=to[i];
		if(d[v]==d[u]+1 && cap[i]>flow[i] && (f=dfs(v,min(minn,cap[i]-flow[i])))>0)
		{
			flow[i]+=f;flow[i^1]-=f;
			ans+=f;minn-=f;
		}
		if(!minn) break;
	}
	return ans;
}
int main()
{
	int n,m,cnt=1000,ans=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j++)
			scanf("%d",&c[i][j]);
	for(int i=1;i<=n;i++) c[i][i]-=a[i];
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j++)
			id[i][j]=++cnt;
	s=cnt+1;t=cnt+2;
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			add(id[i][j],id[i][j-1],1e9),add(id[i][j],id[i+1][j],1e9);
	for(int i=1;i<=n;i++) add(id[i][i],a[i],1e9);
	for(int i=1;i<=1000;i++) add(i,t,m*i*i);
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j++)
			if(c[i][j]>0) add(s,id[i][j],c[i][j]),ans+=c[i][j];
			else add(id[i][j],t,-c[i][j]);
	while(bfs())
	{
		memcpy(cur+1,head+1,sizeof(int)*t);
		ans-=dfs(s,1e9);
	}
	cout<<ans<<endl;
	return 0;
}