ll@h,@w,@a[h*w];
char c[]{};
DijkstraHeap<ll> q[2];
q[0..1].malloc(h*w,1);
q[0].change(0,0);
q[1].change(h*w-1,0);
ll k=0;
for(;;++k){
	ll p=k&1;
	ll i=q[p].pop();
	c[i]=p+1;
	ll y=i/w;
	ll x=i%w;
	if(y)    {ll d=i-w;if(c[d]==2-p)break; q[p].change(d,a[d]);}
	if(y<h-1){ll d=i+w;if(c[d]==2-p)break; q[p].change(d,a[d]);}
	if(x)    {ll d=i-1;if(c[d]==2-p)break; q[p].change(d,a[d]);}
	if(x<w-1){ll d=i+1;if(c[d]==2-p)break; q[p].change(d,a[d]);}
}
wt(k-1);