#include <cstdio>
#include <cstdlib>
#include <climits>
#include <cmath>

#define I_F "queuea.in"
#define O_F "queuea.out"

const int MAXn=1000;
const int P1=1000;
const int P2=5;

struct edge
{
	int x;
	edge *next;
};

int n, m;
short k;
int h[MAXn];
int fam[MAXn][MAXn];
edge *map[MAXn]={NULL};
int d[MAXn]={0}, c[MAXn];
int g[MAXn][MAXn];
int l[MAXn]={0};
long min1[MAXn];
long min2[MAXn][MAXn];
long ans;

void Input();
void Getmap();
void Topdev();
template<typename Any>
inline void Swap(Any&, Any&);
template<typename Any>
void Arrcpy(const Any*, Any*, const int&, const int=-1, const int=-1);
template<typename Any>
inline Any Min(const Any&, const Any&);
long Rand1(int*, const int&);
long Rand2(int*, const int&, const long);
void Search();
void Output();

int main()
{
	Input();
	Getmap();
	Topdev();
	Search();
	Output();
	return 0;
}

void Input()
{
	freopen(I_F,"r",stdin);
	scanf("%d%hd",&n,&k);
	for (int i=0; i<n; ++i)
		scanf("%d",&h[i]);
	for (int i=0; i<n; ++i)
		for (int j=0; j<n; ++j)
			scanf("%d",&fam[i][j]);
}

void Getmap()
{
	edge *temp;
	for (int i=0; i<n; ++i)
		for (int j=i+1; j<n; ++j)
			if (h[j]-h[i]>=k)
			{
				++d[j];
				temp=map[i];
				map[i]=new edge;
				map[i]->x=j;
				map[i]->next=temp;
			}
}

void Topdev()
{
	m=n;
	bool flag=true;
	edge *temp;
	for (int i=0; i<n && flag; ++i)
	{
		flag=false;
		for (int j=0; j<n; ++j)
			if (d[j]==0)
				g[i][l[i]++]=j,
				flag=true;
		for (int j=0; j<l[i]; ++j)
		{
			d[g[i][j]]=-1;
			c[g[i][j]]=i;
			while (map[g[i][j]]!=NULL)
			{
				--d[map[g[i][j]]->x];
				temp=map[g[i][j]];
				map[g[i][j]]=map[g[i][j]]->next;
				delete temp;
			}
		}
		if (!flag)
			m=i;
	}
}

template<typename Any>
inline void Swap(Any &a, Any &b)
{
	Any t=a;
	a=b;
	b=t;
}

template<typename Any>
void Arrcpy(const Any *a, Any *b, const int &l, const int ri=-1, const int le=-1)
{
	for (int i=0; i<l; ++i)
		b[i]=a[i];
	if (le>=0)
		Swap(b[le],b[0]);
	if (ri>=0)
		Swap(b[ri],b[l-1]);
}

template<typename Any>
inline Any Min(const Any &a, const Any &b)
{
	return (a<b)?a:b;
}

long Rand1(int *s, const int &l)
{
	if (l>3)
	{
		int a, b;
		for (int i=0; i<2*sqrt(l); ++i)
		{
			a=1+rand()%(l-2);
			b=1+rand()%(l-2);
			Swap(s[a],s[b]);
		}
	}
	long t=0;
	for (int i=1; i<l; ++i)
		t+=fam[s[i-1]][s[i]];
	return t;
}

long Rand2(int *s, const int &l, const long x)
{
	if (l>3)
	{
		int a, b;
		a=1+rand()%(l-2);
		for (b=1+rand()%(l-2); b==a; b=1+rand()%(l-2));
		if (b<a)
			Swap(a,b);
		long t=x;
		if (a>0)
			t=t-fam[s[a-1]][s[a]]+fam[s[a-1]][s[b]];
		if (b<l-1)
			t=t-fam[s[b+1]][s[b]]+fam[s[b+1]][s[a]];
		if (t<x)
			for (int i=a; i<a+(b-a+1)/2; ++i)
				Swap(s[i],s[b+a-i]);
		else if (rand()%P1<P2)
			for (int i=a; i<a+(b-a+1)/2; ++i)
				Swap(s[i],s[b+a-i]);
		else
			return x;
		return t;
	}
	else
		return x; 
}

void Search()
{
	long now;
	int w[MAXn];
	long t[MAXn];
	for (int i=0; i<l[0]; ++i)
		if (h[g[0][i]]<h[g[0][0]])
			Swap(g[0][i],g[0][0]);
	if (l[0]>1)
	{
		for (int i=1; i<l[0]; ++i)
		{
			min1[i]=LONG_MAX;
			Arrcpy(g[0],w,l[0],i);
			for (int p=0; p<2*log2(l[0]); ++p)
			{
				now=Rand1(w,l[0]);
				for (int q=0; q<2*sqrt(l[0]); ++q)
				{
					now=Rand2(w,l[0],now);
					min1[i]=Min(min1[i],now);
				}
			}
		}
		min1[0]=-1;
	}
	else
		min1[0]=0;
	
	for (int i=1; i<m; ++i)
	{
		if (l[i]>1)
		{
			for (int j=0; j<l[i]; ++j)
				for (int k=0; k<l[i]; ++k)
					if (j!=k)
					{
						Arrcpy(g[i],w,l[i],k,j);
						for (int p=0; p<2*log2(l[i]); ++p)
						{
							now=Rand1(w,l[i]);
							for (int q=0; q<2*sqrt(l[i]); ++q)
							{
								now=Rand2(w,l[i],now);
								min2[j][k]=Min(min2[j][k],now);
							}
						}
					}
		}
		else
			min2[0][0]=0;
		for (int j=0; j<l[i]; ++j)
		{
			t[j]=LONG_MAX;
			for (int k=0; k<l[i-1]; ++k)
				for (int o=0; o<l[i]; ++o)
					if (min1[k]>=0 && min2[o][j]>=0)
						t[j]=Min(t[j],min1[k]+min2[o][j]+fam[g[i-1][k]][g[i][o]]);
			Arrcpy(t,min1,l[i]);
		}
	}
	
	ans=LONG_MAX;
	for (int i=0; i<l[m-1]; ++i)
		ans=Min(ans,min1[i]);
}

void Output()
{
	freopen(O_F,"w",stdout);
	printf("%ld\n",ans);
}