#include <iostream>
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string>
#include <tuple>
#include <vector>
#include <map>
#include <unordered_map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <cassert>
using namespace std;
#define LL long long
#define MP(a, b) make_pair(a, b)
#define POWER9 1000000000
#define MOD POWER9+7
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483647
#define INT_MAX 2147483647
#define LL_MIN (LL)-9223372036854775807
#define LL_MAX (LL)9223372036854775807
#define PI 3.14159265359

int H,W;
int mp[1000][1000];
int cost[1000][1000][32];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> H >> W;
    for(int i=0; i<H; i++){
        for(int j=0; j<W; j++){
            char c;
            cin >> c;
            if(c == '.') mp[i][j] = 0;
            else mp[i][j] = c - '0';
            for(int k=0; k<32; k++) cost[i][j][k] = INT_MAX;
        }
    }
    cost[0][0][0] = 0;

    priority_queue<pair<int,pair<pair<int,int>,int> > > que;
    que.push(MP(INT_MAX, MP(MP(0,0), 0)));
    while(!que.empty()){
        int c = INT_MAX-que.top().first;
        int y = que.top().second.first.first;
        int x = que.top().second.first.second;
        int s = que.top().second.second;
        que.pop();
        if(cost[y][x][s] < c) continue;
        if(y==H-1 && x==W-1){
            cout << c << endl;
            return 0;
        }
        int d[5];
        for(int i=0; i<5; i++){
            d[i] = (s>>(4-i)) % 2;
        }

        int nc = 0;
        if(d[0] == 0) nc += mp[y][x];
        if(d[2] == 0 && y-1 >= 0) nc += mp[y-1][x];
        if(d[3] == 0 && x-1 >= 0) nc += mp[y][x-1];
        if(y+1 < H) nc += mp[y+1][x];
        if(x+1 < W) nc += mp[y][x+1];

        int tmpY = (d[4]==1 ? 2 : 0);
        int tmpX = (d[1]==1 ? 4 : 0);
        if(d[2] == 0 && y-1 >= 0){
            nc -= mp[y-1][x];
            if(y+1 < H && cost[y+1][x][16+8+4+tmpY] > c+nc){
                cost[y+1][x][16+8+4+tmpY] = c+nc;
                que.push(MP(INT_MAX-c-nc, MP(MP(y+1, x), 16+8+4+tmpY)));
            }
            if(x+1 < W && cost[y][x+1][16+2+1+tmpX] > c+nc){
                cost[y][x+1][16+2+1+tmpX] = c+nc;
                que.push(MP(INT_MAX-c-nc, MP(MP(y, x+1), 16+2+1+tmpX)));
            }
            nc += mp[y-1][x];
        }
        if(d[3] == 0 && x-1 >= 0){
            nc -= mp[y][x-1];
            if(y+1 < H && cost[y+1][x][16+8+4+tmpY] > c+nc){
                cost[y+1][x][16+8+4+tmpY] = c+nc;
                que.push(MP(INT_MAX-c-nc, MP(MP(y+1, x), 16+8+4+tmpY)));
            }
            if(x+1 < W && cost[y][x+1][16+2+1+tmpX] > c+nc){
                cost[y][x+1][16+2+1+tmpX] = c+nc;
                que.push(MP(INT_MAX-c-nc, MP(MP(y, x+1), 16+2+1+tmpX)));
            }
            nc += mp[y][x-1];
        }
        if(y+1 < H){
            nc -= mp[y+1][x];
            if(y+1 < H && cost[y+1][x][8+4+tmpY] > c+nc){
                cost[y+1][x][8+4+tmpY] = c+nc;
                que.push(MP(INT_MAX-c-nc, MP(MP(y+1, x), 8+4+tmpY)));
            }
            if(x+1 < W && cost[y][x+1][16+2+tmpX] > c+nc){
                cost[y][x+1][16+2+tmpX] = c+nc;
                que.push(MP(INT_MAX-c-nc, MP(MP(y, x+1), 16+2+tmpX)));
            }
            nc += mp[y+1][x];
        }
        if(x+1 < W){
            nc -= mp[y][x+1];
            if(y+1 < H && cost[y+1][x][16+4+tmpY] > c+nc){
                cost[y+1][x][16+4+tmpY] = c+nc;
                que.push(MP(INT_MAX-c-nc, MP(MP(y+1, x), 16+4+tmpY)));
            }
            if(x+1 < W && cost[y][x+1][2+1+tmpX] > c+nc){
                cost[y][x+1][2+1+tmpX] = c+nc;
                que.push(MP(INT_MAX-c-nc, MP(MP(y, x+1), 2+1+tmpX)));
            }
            nc += mp[y][x+1];
        }
    }

    return 0;
}


Measured memory_bytes: 132796