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>
//package Codeforces.Round719Div3;

import java.io.*;
import java.util.*;

public class G {
    static class Node{
        int x;
        int y;
        long[] dir;
        long val;
        Node(int x, int y, long val){
            this.x = x;
            this.y = y;
            this.val = val;
            this.dir = new long[]{Long.MAX_VALUE/100, Long.MAX_VALUE/100};
        }
    }
    static class Portals implements Comparable<Portals>{
        long startdist;
        long enddist;
        Portals(long startdist, long enddist){
            this.startdist = startdist;
            this.enddist = enddist;
        }
        public int compareTo(Portals p){
            return Long.compare(this.enddist, p.enddist);
        }
    }
    static boolean isValid(int n, int m, int x, int y){
        return 0<=x && x<n && 0<=y && y<m;
    }
    static void bfs(Node[][] nodes, int startx, int starty, int dir, long w){
        Queue<Node> q = new LinkedList<>();

        int n = nodes.length;
        int m = nodes[0].length;
        boolean[][] isVisited = new boolean[n][m];

        Node startnode = nodes[startx][starty];
        isVisited[startx][starty] = true;
        q.add(startnode);
        startnode.dir[dir] = 0;

        while(!q.isEmpty()){
            Node cnode = q.remove();

            if(isValid(n, m, cnode.x+1, cnode.y)
                    && !isVisited[cnode.x+1][cnode.y] && nodes[cnode.x+1][cnode.y].val!=-1){
                Node next = nodes[cnode.x+1][cnode.y];
                next.dir[dir] = cnode.dir[dir]+w;
                isVisited[next.x][next.y] = true;
                q.add(next);
            }

            if(isValid(n, m, cnode.x-1, cnode.y)
                    && !isVisited[cnode.x-1][cnode.y] && nodes[cnode.x-1][cnode.y].val!=-1){
                Node next = nodes[cnode.x-1][cnode.y];
                next.dir[dir] = cnode.dir[dir]+w;
                isVisited[next.x][next.y] = true;
                q.add(next);
            }

            if(isValid(n, m, cnode.x, cnode.y+1)
                    && !isVisited[cnode.x][cnode.y+1] && nodes[cnode.x][cnode.y+1].val!=-1){
                Node next = nodes[cnode.x][cnode.y+1];
                next.dir[dir] = cnode.dir[dir]+w;
                isVisited[next.x][next.y] = true;
                q.add(next);
            }

            if(isValid(n, m, cnode.x, cnode.y-1)
                    && !isVisited[cnode.x][cnode.y-1] && nodes[cnode.x][cnode.y-1].val!=-1){
                Node next = nodes[cnode.x][cnode.y-1];
                next.dir[dir] = cnode.dir[dir]+w;
                isVisited[next.x][next.y] = true;
                q.add(next);
            }
        }
    }
    public static void main(String[] args) throws IOException {
        //long start = System.currentTimeMillis();
        Soumit sc = new Soumit();
        
        int n = sc.nextInt();
        int m = sc.nextInt();
        int w = sc.nextInt();
        long[][] mat = new long[n][m];
        for(int i=0;i<n;i++){
            mat[i] = sc.nextLongArray(m);
        }

        Node[][] nodes = new Node[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                nodes[i][j] = new Node(i, j, mat[i][j]);
            }
        }

        //long s1 = System.currentTimeMillis();
        bfs(nodes, 0, 0, 0, w);
        bfs(nodes, n-1, m-1, 1, w);
        /*long e1 = System.currentTimeMillis();
        System.out.println((e1-s1)/1000.0);*/

        /*ArrayList<Portals> portals = new ArrayList<>();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                Node node = nodes[i][j];
                if (node.val > 0) {
                    portals.add(new Portals(node.dir[0]+node.val, node.dir[1]+node.val));
                }
            }
        }*/

        long min = nodes[0][0].dir[1];
        long end_min = Long.MAX_VALUE;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(nodes[i][j].val>0)
                    end_min = Math.min(end_min, nodes[i][j].dir[1]+nodes[i][j].val);
            }
        }

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(nodes[i][j].val>0)
                    min = Math.min(min, end_min+nodes[i][j].dir[0]+nodes[i][j].val);
            }
        }

        if(min>1e16)
            System.out.println(-1);
        else System.out.println(min);

        /*long end = System.currentTimeMillis();
        System.out.println((end-start)/1000.0);*/
        
        sc.close();
    }
    static class Soumit {
        final private int BUFFER_SIZE = 1 << 18;
        final private DataInputStream din;
        final private byte[] buffer;
        private PrintWriter pw;
        private int bufferPointer, bytesRead;
        StringTokenizer st;

        public Soumit() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Soumit(String file_name) throws IOException {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public void streamOutput(String file) throws IOException {
            FileWriter fw = new FileWriter(file);
            BufferedWriter bw = new BufferedWriter(fw);
            pw = new PrintWriter(bw);
        }

        public void println(String a) {
            pw.println(a);
        }

        public void print(String a) {
            pw.print(a);
        }

        public String readLine() throws IOException {
            byte[] buf = new byte[3000064]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

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

        public void sort(int[] arr) {
            ArrayList<Integer> arlist = new ArrayList<>();
            for (int i : arr)
                arlist.add(i);

            Collections.sort(arlist);
            for (int i = 0; i < arr.length; i++)
                arr[i] = arlist.get(i);
        }

        public void sort(long[] arr) {
            ArrayList<Long> arlist = new ArrayList<>();
            for (long i : arr)
                arlist.add(i);

            Collections.sort(arlist);
            for (int i = 0; i < arr.length; i++)
                arr[i] = arlist.get(i);
        }

        public int[] nextIntArray(int n) throws IOException {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = nextInt();
            }

            return arr;
        }

        public long[] nextLongArray(int n) throws IOException {
            long[] arr = new long[n];
            for (int i = 0; i < n; i++) {
                arr[i] = nextLong();
            }

            return arr;
        }

        public double[] nextDoubleArray(int n) throws IOException {
            double[] arr = new double[n];
            for (int i = 0; i < n; i++) {
                arr[i] = nextDouble();
            }

            return arr;
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();

            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');

            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            /*if (din == null)
                return;*/
            if (din != null) din.close();
            if (pw != null) pw.close();
        }
    }
}
