Problem: problem

The city of IOI, where JOI lives, has a rectangular shape with H sections in the north-south direction and W sections in the east-west direction, and is divided into H x W sections. The i-th section from the north and the j-th section from the west are represented as (i, j). A large-scale festival is currently being held to commemorate the international programming contest held in IOI City. There are food stalls in some areas, each selling different types of sweets. There are no food stalls in plots (1, 1), plots (H, W) and the plots adjacent to them north, south, east and west.

JOI moves from compartment (1, 1) to compartment (H, W). To shorten the travel time, JOI travels only to the east or south. JOI likes sweets, so he takes the following actions in order each time he enters a section.

1. If there is a stall selling sweets that you have not bought yet in the current section, buy sweets at that stall.
2. If there are food stalls selling sweets that you have not bought yet in the area adjacent to the north, south, east, and west of the current area, call a salesperson from all the stalls except one of those stalls. Buy sweets.



JOI never buys the same kind of sweets more than once.

Given the size of the IOI city, the location of the stalls, and the price of the sweets at each stall, the sweets that JOI buys while moving from parcel (1, 1) to parcel (H, W). Find the minimum value of the total amount of.





Example

Input

5 5
..483
.59.9
3.866
79...
4.8..


Output

20

Solution (in CPP):

Solution:
//q6.cpp

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define debug(x) cerr << #x << " = " << x << endl;


#define mod 1000000007 //1e9+7
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 1010
#define BSIZE 32 //2^5

int dp[SIZE][SIZE][BSIZE][2];

inline int make_bit(int e,int d,int c,int b,int a){
    return a*16 + b*8 + c*4 + d*2 + e;
}

int main(){
    int h,w;
    char price[SIZE][SIZE];
    
    scanf("%d%d",&h,&w);
    
    for(int i=0;i<h;i++){
        scanf("%s",price[i]);
    }
    
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            for(int k=0;k<BSIZE;k++){
                dp[i][j][k][0] = dp[i][j][k][1] = INF;
            }
        }
    }
    
    dp[0][0][0][0] = dp[0][0][0][1] = 0;
    
    
    int index_y[2][5] = {{0,1,1,2,2},{0,0,1,1,1}};
    int index_x[2][5] = {{1,0,1,0,1},{1,2,0,1,2}};
    int mo[5] = {0,-1,0,1,0};
    
    
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            for(int k=0;k<BSIZE;k++){
                for(int l=0;l<2;l++){
                    if(dp[i][j][k][l]==INF) continue;
                    
                    int b = k;
                    int data[3][3],next_data[3][3];
                    
                    for(int t=0;t<9;t++){
                        data[t/3][t%3] = 0;
                    }
                    
                    for(int t=0;t<5;t++){
                        data[index_y[l][t]][index_x[l][t]] = b%2;
                        b/=2;
                    }
                    
                    for(int t=0;t<9;t++){
                        next_data[t/3][t%3] = data[t/3][t%3];
                    }
                    
                    int add_cost = 0;
                    
                    int count = 0;
                    
                    for(int t=0;t<4;t++){
                        if(0<=i+mo[t] && i+mo[t]<h && 0<=j+mo[t+1] && j+mo[t+1]<w)
                            if(price[i+mo[t]][j+mo[t+1]]!='.' && data[mo[t]+1][mo[t+1]+1]==0){
                                add_cost += price[i+mo[t]][j+mo[t+1]]-'0';
                                next_data[mo[t]+1][mo[t+1]+1] = 1;
                                count++;
                            }
                    }
                    
                    if(count<=1) add_cost = 0;
                    
                    if(data[1][1]==0 && price[i][j]!='.'){
                        add_cost += price[i][j]-'0';
                        data[1][1] = 1;
                    }
                    
                    next_data[1][1] = 1;
                    
                    if(count <= 1){
                        int next_bit;
                        
                        if(j<w-1){
                            next_bit = make_bit(data[0][2],data[1][1],data[1][2],data[2][1],data[2][2]);
                            
                            
                            dp[i][j+1][next_bit][0] = min(dp[i][j+1][next_bit][0],dp[i][j][k][l]+add_cost);
                        }
                        
                        if(i<h-1){
                            next_bit = make_bit(data[1][1],data[1][2],data[2][0],data[2][1],data[2][2]);
                            
                            dp[i+1][j][next_bit][1] = min(dp[i+1][j][next_bit][1],dp[i][j][k][l]+add_cost);
                        }
                        
                    }else{
                        
                        
                        for(int t=0;t<4;t++){
                            if(0<=i+mo[t] && i+mo[t]<h && 0<=j+mo[t+1] && j+mo[t+1]<w){
                                if(price[i+mo[t]][j+mo[t+1]]!='.' && data[mo[t]+1][mo[t+1]+1]==0){
                                    next_data[mo[t]+1][mo[t+1]+1] = 0;
                                    int next_cost = dp[i][j][k][l] + add_cost - (price[i+mo[t]][j+mo[t+1]]-'0');
                                    
                                    int next_bit;
                                    
                                    if(j<w-1){
                                        //??????
                                        next_bit = make_bit(next_data[0][2],next_data[1][1],next_data[1][2],next_data[2][1],next_data[2][2]);
                                        
                                        dp[i][j+1][next_bit][0] = min(dp[i][j+1][next_bit][0],next_cost);
                                        
                                        
                                    }
                                    
                                    if(i<h-1){
                                        //??????
                                        next_bit = make_bit(next_data[1][1],next_data[1][2],next_data[2][0],next_data[2][1],next_data[2][2]);
                                        
                                        dp[i+1][j][next_bit][1] = min(dp[i+1][j][next_bit][1],next_cost);
                                    }
                                    
                                    next_data[mo[t]+1][mo[t+1]+1] = 1;
                                }
                            }
                        }
                        
                    }
                    
                }
            }
        }
    }
    
    int ans = INF;
    /*
     for(int i=0;i<h;i++){
     for(int j=0;j<w;j++){
     int p = INF;
     for(int k=0;k<BSIZE;k++){
     p = min(p,min(dp[i][j][k][0],dp[i][j][k][1]));
     }
     fprintf(stderr,"%d ",p);
     }
     fprintf(stderr,"\n");
     }
     */
    for(int i=0;i<BSIZE;i++){
        ans = min(ans,min(dp[h-1][w-1][i][0],dp[h-1][w-1][i][1]));
    }
    
    printf("%d\n",ans);
    
    return 0;
}