RT.
AC 了，但是时限 3s，我跑了接近 2s，这要是 python 选手就寄了。
$O(nm)$ 做法，不明白哪里没写好。

#pragma GCC optimize("Ofast")
#define __vector__
#ifdef __vector__
#include <iostream>
#include <iomanip>
#include <string>
#include <cstring>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cassert>
#include <random>
#include <numeric>
#include <complex>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <ext/rope>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define REP(i, a, b) for (int i = a; i >= b; i--)
#define pb push_back
#define eb emplace_back
#define popcount __builtin_popcount
#define ctz __builtin_ctz
#define gc getchar()
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
template <class T>
void write(T x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x >= 10)
    {
        write(x / 10);
    }
    putchar(x % 10 ^ 48);
}
template <class T>
void read(T &x)
{
    x = 0;
    T f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    x *= f;
}
template <class T>
T quick_pow(T a, T b, T p = -1)
{
    if (p == -1)
    {
        T res = 1;
        while (b)
        {
            if (b & 1)
                res = res * a;
            a *= a;
            b >>= 1;
        }
        return res;
    }
    else
    {
        T res = 1;
        while (b)
        {
            if (b & 1)
                res = res * a % p;
            a = a * a % p;
            b >>= 1;
        }
        return res;
    }
}
template <class T>
T inv(T x, T p)
{
    return quick_pow(x, p - 2, p);
}
struct Matrix
{
    std::vector<std::vector<ll>> mp;
    ll p;
    int size;
    void init(int siz, ll mod = -1, bool isdw = 0)
    { // 第二个参数：是否设为单位矩阵
        p = mod;
        size = siz;
        mp.resize(siz);
        for (int i = 0; i < siz; i++)
        {
            mp[i].resize(siz);
            for (int j = 0; j < siz; j++)
            {
                mp[i][j] = 0;
            }
            if (isdw)
                mp[i][i] = 1;
        }
    }
    Matrix operator*(const Matrix &b)
    {
        Matrix res;
        res.init(std::max(size, b.size), p);
        for (int i = 0; i < size; i++)
        {
            for (int k = 0; k < size; k++)
            {
                for (int j = 0; j < size; j++)
                {
                    if (k >= b.size || j >= b.size)
                        continue;
                    res.mp[i][j] += mp[i][k] * b.mp[k][j];
                    if (res.p != -1)
                        res.mp[i][j] %= res.p;
                }
            }
        }
        return res;
    }
};
Matrix quick_pow_mat(Matrix a, ll b)
{
    Matrix res;
    res.init(a.size, a.p, 1);
    while (b)
    {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
#endif
//=============前面都是模板=======
const int maxn=2e3+5;
int n,m,w;
ll a[maxn][maxn];
ll dis[maxn][maxn];
bool vis[maxn][maxn];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,1,-1};
struct Node
{
    int i,j;
}q[maxn*maxn*4];
void bfs(Node start)
{
    memset(vis,0,sizeof vis);
    memset(dis,0x7f,sizeof dis);
    int head=1,tail=0;
    q[++tail]=start;
    dis[start.i][start.j]=0;
    while(head<=tail)
    {
        auto u=q[head++];
        if(vis[u.i][u.j])continue;
        vis[u.i][u.j]=1;
        for(int i=0;i<4;i++)
        {
            int fx=u.i+dx[i];
            int fy=u.j+dy[i];
            if(fx<1||fy<1||fx>n||fy>m||a[fx][fy]==-1)continue;
            if(dis[fx][fy]>dis[u.i][u.j]+ll(w))
            {
                if(dis[fx][fy]==dis[0][0])
                    q[++tail]=Node{fx,fy};
                dis[fx][fy]=dis[u.i][u.j]+(ll)w;
            }
        }
    }
}
int main()
{
    read(n);
    read(m);
    read(w);
    FOR(i,1,n)
    {
        FOR(j,1,m)
        {
            read(a[i][j]);
        }
    }
    if(a[1][1]==-1||a[n][m]==-1)
    {
        printf("-1\n");
        return 0;
    }
    ll ans=1e18;
    bfs(Node{1,1});
    if(vis[n][m])
    {
        ans=dis[n][m];
    }
    ll res=1e18;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]>0)
                res=std::min(res,dis[i][j]+a[i][j]);
        }
    }
    bfs(Node{n,m});
    ll res2=1e18;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]>0)
                res2=std::min(res2,dis[i][j]+a[i][j]);
        }
    }
    ans=std::min(ans,res+res2);
    if(ans==1e18)printf("-1");
    else printf("%lld",ans);
    return 0;
}