Dima overslept the alarm clock, which was supposed to raise him to school.

Dima wonders if he will have time to come to the first lesson. To do this, he needs to know the minimum time it will take him to get from home to school.

The city where Dima lives is a rectangular field of n × m size. Each cell (i, j) on this field is denoted by one number a_{ij}:

  * The number -1 means that the passage through the cell is prohibited; 
  * The number 0 means that the cell is free and Dima can walk though it. 
  * The number x (1 ≤ x ≤ 10^9) means that the cell contains a portal with a cost of x. A cell with a portal is also considered free. 



From any portal, Dima can go to any other portal, while the time of moving from the portal (i, j) to the portal (x, y) corresponds to the sum of their costs a_{ij} + a_{xy}.

In addition to moving between portals, Dima can also move between unoccupied cells adjacent to one side in time w. In particular, he can enter a cell with a portal and not use it.

Initially, Dima is in the upper-left cell (1, 1), and the school is in the lower right cell (n, m).

Input

The first line contains three integers n, m and w (2 ≤ n, m ≤ 2 ⋅ 10^3, 1 ≤ w ≤ 10^9), where n and m are city size, w is time during which Dima moves between unoccupied cells.

The next n lines each contain m numbers (-1 ≤ a_{ij} ≤ 10^9) — descriptions of cells.

It is guaranteed that the cells (1, 1) and (n, m) are free.

Output

Output the minimum time it will take for Dima to get to school. If he cannot get to school at all, then output "-1".

Example

Input


5 5 1
0 -1 0 1 -1
0 20 0 0 -1
-1 -1 -1 -1 -1
3 0 0 0 0
-1 0 0 0 0


Output


14

Note

Explanation for the first sample: 

<image>
import java.io.*;
import java.util.*;
import java.math.*;
import java.math.BigInteger;


public final class A
{    
	static StringBuilder ans=new StringBuilder();
	static FastReader in=new FastReader();
	static ArrayList<ArrayList<Integer>> g,tg;
	static long mod=(long)1e9+7,INF=Long.MAX_VALUE;
	static boolean set[],col[]; 
	static int D[],par[];
	static long G[][];
	static long dp[][],max=0;
	static  HashMap<Integer,Long> buy,sell;
	static pair moves[]= {new pair(-1,0),new pair(1,0), new pair(0,-1), new pair(0,1)};
	public static void main(String args[])throws IOException
	{		
		int N=i(),M=i();
		long w=l();
		G=new long[N][M];
		long D1[][]=new long[N][M];
		long D2[][]=new long[N][M];
		long A=INF,B=INF;
		for(int i=0; i<N; i++) 
		{
			for(int j=0; j<M; j++)
			{
				D1[i][j]=INF;
				D2[i][j]=INF;
				G[i][j]=l();
			}
		}
		Queue<Integer> x=new LinkedList<Integer>();
		Queue<Integer> y=new LinkedList<Integer>();
		x.add(0);y.add(0); D1[0][0]=0;
		while(x.size()>0)
		{
			int i=x.remove(),j=y.remove();
			if(G[i][j]>0)A=Math.min(A, G[i][j]+D1[i][j]);
			for(pair c:moves)
			{
				if(isValid(i+c.a,j+c.b,N,M))
				{
					if(D1[i+c.a][j+c.b]>w+D1[i][j])
					{
						D1[i+c.a][j+c.b]=w+D1[i][j];
						x.add(i+c.a);
						y.add(j+c.b);
					}
				}
			}
		}
		if(A==INF)
		{
			if(D1[N-1][M-1]==INF)System.out.println(-1);
			else System.out.println(D1[N-1][M-1]);
			return;
		}
		x.add(N-1);y.add(M-1);
		D2[N-1][M-1]=0;
		while(x.size()>0)
		{
			int i=x.remove(),j=y.remove();
			if(G[i][j]>0)B=Math.min(B, G[i][j]+D2[i][j]);
			for(pair c:moves)
			{
				if(isValid(i+c.a,j+c.b,N,M))
				{
					if(D2[i+c.a][j+c.b]>w+D2[i][j])
					{
						D2[i+c.a][j+c.b]=w+D2[i][j];
						x.add(i+c.a);
						y.add(j+c.b);
					}
				}
			}
		}
		// System.out.println(A+" "+B);
		// for(long a[]:D1)print(a);
		if(A<INF && B<INF)
		{
			
			if(D1[N-1][M-1]>A+B)
			{
				D1[N-1][M-1]=A+B;
			}
		}
		if(D1[N-1][M-1]==INF)System.out.println(-1);
		else System.out.println(D1[N-1][M-1]);
	}
	static boolean isValid(int x,int y,int N,int M)
	{
		if(x<0 || x>=N)return false;
		if(y<0 || y>=M)return false;
		if(G[x][y]==-1)return false;
		return true;
	}
	static boolean equal(long A[],long B[])
	{
		for(int i=0; i<A.length; i++)if(A[i]!=B[i])return false;
		return true;	
	}
	static int lower(long A[],long x)
	{
		int l=-1,r=A.length;
		while(r-l>1)
		{
			int m=(l+r)/2;
			if(A[m]>=x)r=m;
			else l=m;				
		}
		return r;
	}
	static int upper(long A[],long x)
	{
		int l=-1,r=A.length;
		while(r-l>1)
		{
			int m=(l+r)/2;
			if(A[m]<=x)l=m;
			else r=m;
		}
		return l;
	}

	static int max(int a ,int b,int c,int d)
	{
		a=Math.max(a, b);
		c=Math.max(c,d);
		return Math.max(a, c);
	}
	static int min(int a ,int b,int c,int d)
	{
		a=Math.min(a, b);
		c=Math.min(c,d);
		return Math.min(a, c);
	}

	static int find(int l,int r,long A[] ,long val)
	{
		int m=0;
		while(l<=r)
		{
			m=(l+r)/2;
			if(A[m]>=val)r=m-1;
			else l=m+1;
		}
		return m;
	}
	static void dfs(int n,int p)
	{
		par[n]=p;
		set[n]=true;
		for(int c:g.get(n))
		{
			if(!set[c])dfs(c,n);
		}
	}
	static HashMap<Integer,Integer> Hash(int A[])
	{
		HashMap<Integer,Integer> mp=new HashMap<>();
		for(int a:A)
		{
			int f=mp.getOrDefault(a,0)+1;
			mp.put(a, f);
		}
		return mp;
	}
	static long mul(long a, long b)
	{
		return ( a %mod * 1L * b%mod )%mod;
	}
	static void swap(int A[],int a,int b)
	{
		int t=A[a];
		A[a]=A[b];
		A[b]=t;
	}


	static int find(int a)
	{
		if(par[a]<0)return a;
		return par[a]=find(par[a]);
	}
	static void union(int a,int b)
	{
		a=find(a);
		b=find(b);
		if(a!=b)
		{
			par[a]+=par[b];
			par[b]=a;
		}
	}
	static boolean isSorted(int A[])
	{
		for(int i=1; i<A.length; i++)
		{
			if(A[i]<A[i-1])return false;
		}
		return true;
	}

	static boolean isDivisible(StringBuilder X,int i,long num)
	{
		long r=0;
		for(; i<X.length(); i++)
		{
			r=r*10+(X.charAt(i)-'0');
			r=r%num;
		}
		return r==0;
	}    



	static int lower_Bound(int A[],int low,int high, int x) 
	{ 
		if (low > high) 
			if (x >= A[high]) 
				return A[high]; 

		int mid = (low + high) / 2; 

		if (A[mid] == x) 
			return A[mid]; 

		if (mid > 0 && A[mid - 1] <= x && x < A[mid]) 
			return A[mid - 1]; 

		if (x < A[mid]) 
			return lower_Bound( A, low, mid - 1, x); 

		return lower_Bound(A, mid + 1, high, x); 
	} 

	static String f(String A)
	{
		String X="";
		for(int i=A.length()-1; i>=0; i--)
		{
			int c=A.charAt(i)-'0';
			X+=(c+1)%2;
		}
		return X;
	}

	static void sort(long[] a) //check for long
	{
		ArrayList<Long> l=new ArrayList<>();
		for (long i:a) l.add(i);
		Collections.sort(l);
		for (int i=0; i<a.length; i++) a[i]=l.get(i);
	}

	static String swap(String X,int i,int j)
	{
		char ch[]=X.toCharArray();
		char a=ch[i];
		ch[i]=ch[j];
		ch[j]=a;
		return new String(ch);
	}

	static int sD(long n)  
	{  

		if (n % 2 == 0 )  
			return 2;  

		for (int i = 3; i * i <= n; i += 2) {  
			if (n % i == 0 )  
				return i;  
		}  

		return (int)n;  
	}  

	static void setGraph(int N)
	{
		par=new int[N+1];
		D=new int[N+1];
		set=new boolean[N+1];
		g=new ArrayList<ArrayList<Integer>>();
		tg=new ArrayList<ArrayList<Integer>>();
		int inf=Integer.MAX_VALUE;
		for(int i=0; i<=N; i++)
		{

			g.add(new ArrayList<Integer>());
			tg.add(new ArrayList<Integer>());			
			D[i]=inf;
		}
	}



	static  long pow(long a,long b)
	{
		//long mod=1000000007;
		long pow=1;
		long x=a;
		while(b!=0)
		{
			if((b&1)!=0)pow=(pow*x)%mod;
			x=(x*x)%mod;
			b/=2;
		}
		return pow;
	}

	static long toggleBits(long x)//one's complement || Toggle bits
	{
		int n=(int)(Math.floor(Math.log(x)/Math.log(2)))+1;

		return ((1<<n)-1)^x;
	}

	static int countBits(long a)
	{
		return (int)(Math.log(a)/Math.log(2)+1);
	}

	static long fact(long N)
	{ 
		long n=2; 
		if(N<=1)return 1;
		else
		{
			for(int i=3; i<=N; i++)n=(n*i)%mod;
		}
		return n;
	}

	static int kadane(int A[])
	{
		int lsum=A[0],gsum=A[0];
		for(int i=1; i<A.length; i++)
		{
			lsum=Math.max(lsum+A[i],A[i]);
			gsum=Math.max(gsum,lsum);
		}
		return gsum;
	}

	static void sort(int[] a) {
		ArrayList<Integer> l=new ArrayList<>();
		for (int i:a) l.add(i);
		Collections.sort(l);
		for (int i=0; i<a.length; i++) a[i]=l.get(i);
	}

	static boolean isPrime(long N)
	{
		if (N<=1)  return false; 
		if (N<=3)  return true; 
		if (N%2 == 0 || N%3 == 0) return false; 
		for (int i=5; i*i<=N; i=i+6) 
			if (N%i == 0 || N%(i+2) == 0) 
				return false; 
		return true; 
	}
	static void print(char A[])
	{
		for(char c:A)System.out.print(c+" ");
		System.out.println();
	}
	static void print(boolean A[])
	{
		for(boolean c:A)System.out.print(c+" ");
		System.out.println();
	}
	static void print(int A[])
	{
		for(int a:A)System.out.print(a+" ");
		System.out.println();	
	}
	static void print(long A[])
	{
		for(long i:A)System.out.print(i+ " ");
		System.out.println();

	}
	static void print(ArrayList<Integer> A)
	{
		for(int a:A)System.out.print(a+" ");
		System.out.println();
	}

	static int i()
	{
		return in.nextInt();
	}

	static long l()
	{
		return in.nextLong();
	}

	static int[] input(int N){
		int A[]=new int[N];
		for(int i=0; i<N; i++)
		{
			A[i]=in.nextInt();
		}
		return A;
	}

	static long[] inputLong(int N)     {
		long A[]=new long[N];
		for(int i=0; i<A.length; i++)A[i]=in.nextLong();
		return A;
	}

	static long GCD(long a,long b) 
	{
		if(b==0)
		{
			return a;
		}
		else return GCD(b,a%b );
	}

}
class cube implements Comparable<cube>
{
	int a, b,index;
	cube(int a,int b,int index)
	{
		this.index=index;
		this.a=a;
		this.b=b;
	}
	public int compareTo(cube X)
	{
		if(X.a==this.a)return this.b-X.b;
		return this.a-X.a;
	}
}
class pair implements Comparable<pair>
{
	int a, b;
	pair(int a,int i)
	{
		this.a=a;
		b=i;
	}
	public int compareTo(pair X)
	{
		return this.a-X.a;
	}
}

//Code For FastReader
//Code For FastReader
//Code For FastReader
//Code For FastReader
class FastReader
{
	BufferedReader br;
	StringTokenizer st;
	public FastReader()
	{
		br=new BufferedReader(new InputStreamReader(System.in));
	}

	String next()
	{
		while(st==null || !st.hasMoreElements())
		{
			try
			{
				st=new StringTokenizer(br.readLine());
			}
			catch(IOException e)
			{
				e.printStackTrace();
			}
		}
		return st.nextToken();
	}

	int nextInt()
	{
		return Integer.parseInt(next());
	}

	long nextLong()
	{
		return Long.parseLong(next());
	}

	double nextDouble()
	{
		return Double.parseDouble(next());
	}

	String nextLine()
	{
		String str="";
		try
		{
			str=br.readLine();
		}
		catch (IOException e)
		{
			e.printStackTrace();
		}
		return str;
	}

}