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:
#include <bits/stdc++.h>
                                        #include<iostream>
                                        #include<cstdio>
                                        #include<vector>
                                        #include<queue>
                                        #include<map>
                                        #include<cstring>
                                        #include<string>
                                        #include <math.h>
                                        #include<algorithm>
                                    //    #include <boost/multiprecision/cpp_int.hpp>
                                        #include<functional>
                        //       #define int long long
                                        #define inf  1000000007
                                        #define pa pair<int,int>
                                        #define ll long long
                                        #define pal pair<double,double>
                                        #define ppap pair<pa,int>
                                  
                                        #define ssa pair<string,int>
                                        #define  mp make_pair
                                        #define  pb push_back
                                        #define EPS (1e-7)
                                        #define equals(a,b) (fabs((a)-(b))<EPS)
int dx[4]={0,-1,0,1};
int dy[4]={1,0,-1,0};
                                        using namespace std;
                               			class pa3{
                                        	public:
                                        	int x,y,z;
                                        	pa3(int x=0,int y=0,int z=0):x(x),y(y),z(z) {}
                                        	bool operator < (const pa3 &p) const{
                                        		if(x!=p.x) return x<p.x;
                                        		if(y!=p.y) return y<p.y;
                                        		 return z<p.z;
                                        		//return x != p.x ? x<p.x: y<p.y;
                                        	}
                               				bool operator > (const pa3 &p) const{
                                        		if(x!=p.x) return x>p.x;
                                        		if(y!=p.y) return y>p.y;
                                        		 return z>p.z;
                                        		//return x != p.x ? x<p.x: y<p.y;
                                        	}
                                        	bool operator == (const pa3 &p) const{
                                        		return x==p.x && y==p.y && z==p.z;
                                        	}
                                        		bool operator != (const pa3 &p) const{
                                        			return !( x==p.x && y==p.y && z==p.z);
                                        	}
                                        
                                        };
                                        
                                        class pa4{
                                        	public:
                                        	int x;
                                        	int y,z,w;
                                        	pa4(int x=0,int y=0,int z=0,int w=0):x(x),y(y),z(z),w(w) {}
                                        	bool operator < (const pa4 &p) const{
                                        		if(x!=p.x) return x<p.x;
                                        		if(y!=p.y) return y<p.y;
                                        		if(z!=p.z)return z<p.z;
                                        		return w<p.w;
                                        		//return x != p.x ? x<p.x: y<p.y;
                                        	}
                                        	bool operator > (const pa4 &p) const{
                                        		if(x!=p.x) return x>p.x;
                                        		if(y!=p.y) return y>p.y;
                                        		if(z!=p.z)return z>p.z;
                                        		return w>p.w;
                                        		//return x != p.x ? x<p.x: y<p.y;
                                        	}
                                        	bool operator == (const pa4 &p) const{
                                        		return x==p.x && y==p.y && z==p.z &&w==p.w;
                                        	}
                                        		
                                        
                                        };
                                        class pa2{
                                        	public:
                                        	int x,y;
                                        	pa2(int x=0,int y=0):x(x),y(y) {}
                                        	pa2 operator + (pa2 p) {return pa2(x+p.x,y+p.y);}
                                        	pa2 operator - (pa2 p) {return pa2(x-p.x,y-p.y);}
                                        	bool operator < (const pa2 &p) const{
                                        		return x != p.x ? x<p.x: y<p.y;
                                        	}
                                        	bool operator > (const pa2 &p) const{
                                        		return x != p.x ? x>p.x: y>p.y;
                                        	}
                                        	bool operator == (const pa2 &p) const{
                                        		return abs(x-p.x)==0 && abs(y-p.y)==0;
                                        	}
                                        	bool operator != (const pa2 &p) const{
                                        		return !(abs(x-p.x)==0 && abs(y-p.y)==0);
                                        	}
                                        		
                                        
                                        };
                                        
                                               #define ppa pair<int,pas>
                                        class Point{
                                        	public:
                                        	double x,y;
                                        	Point(double x=0,double y=0):x(x),y(y) {}
                                        	Point operator + (Point p) {return Point(x+p.x,y+p.y);}
                                        	Point operator - (Point p) {return Point(x-p.x,y-p.y);}
                                        	Point operator * (double a) {return Point(x*a,y*a);}
                                        	Point operator / (double a) {return Point(x/a,y/a);}
                                        	double absv() {return sqrt(norm());}
                                        	double norm() {return x*x+y*y;}
                                        	bool operator < (const Point &p) const{
                                        		return x != p.x ? x<p.x: y<p.y;
                                        	}
                                        	bool operator == (const Point &p) const{
                                        		return fabs(x-p.x)<EPS && fabs(y-p.y)<EPS;
                                        	}
                                        };
                                        typedef Point Vector;
                                 #define pl pair<int,pas>
                                        struct Segment{
                                        Point p1,p2;
                                        };
                                         double dot(Vector a,Vector b){
                                        	return a.x*b.x+a.y*b.y;
                                        }
                                        double cross(Vector a,Vector b){
                                        	return a.x*b.y-a.y*b.x;
                                        }
                                    
            bool parareru(Point a,Point b,Point c,Point d){
            //	if(abs(cross(a-b,d-c))<EPS)cout<<"dd "<<cross(a-b,d-c)<<endl;
            	return abs(cross(a-b,d-c))<EPS;
            }
            double distance_ls_p(Point a, Point b, Point c) {
              if ( dot(b-a, c-a) < EPS ) return (c-a).absv();
              if ( dot(a-b, c-b) < EPS ) return (c-b).absv();
              return abs(cross(b-a, c-a)) / (b-a).absv();
            }
            bool is_intersected_ls(Segment a,Segment b) {
            	if(a.p1==b.p1||a.p2==b.p1||a.p1==b.p2||a.p2==b.p2) return false;
            	if(parareru((a.p2),(a.p1),(a.p1),(b.p2))&&parareru((a.p2),(a.p1),(a.p1),(b.p1))){
            //		cout<<"sss"<<endl;
            		if(dot(a.p1-b.p1,a.p1-b.p2)<EPS) return true;
            		if(dot(a.p2-b.p1,a.p2-b.p2)<EPS) return true;
            		if(dot(a.p1-b.p1,a.p2-b.p1)<EPS) return true;
            		if(dot(a.p1-b.p2,a.p2-b.p2)<EPS) return true;
            		return false;
            	}
              else return ( cross(a.p2-a.p1, b.p1-a.p1) * cross(a.p2-a.p1, b.p2-a.p1) < EPS ) && ( cross(b.p2-b.p1, a.p1-b.p1) * cross(b.p2-b.p1, a.p2-b.p1) < EPS );
            }
             
            double segment_dis(Segment a,Segment b){
            	if(is_intersected_ls(a,b))return 0;
            	double r=distance_ls_p(a.p1, a.p2, b.p1);
            	r=min(r,distance_ls_p(a.p1, a.p2, b.p2));
            	r=min(r,distance_ls_p(b.p1, b.p2, a.p2));
            	r=min(r,distance_ls_p(b.p1, b.p2, a.p1));
            	return r;
            }
            Point intersection_ls(Segment a, Segment b) {
              Point ba = b.p2-b.p1;
              double d1 = abs(cross(ba, a.p1-b.p1));
              double d2 = abs(cross(ba, a.p2-b.p1));
              double t = d1 / (d1 + d2);
             
              return a.p1 + (a.p2-a.p1) * t;
            }
             
                            string itos( int i ) {
                            ostringstream s ;
                            s << i ;
                            return s.str() ;
                            }
                             
                            int gcd(int v,int b){
                            	if(v>b) return gcd(b,v);
                            	if(v==b) return b;
                            	if(b%v==0) return v;
                            	return gcd(v,b%v);
                            }
             
                            double distans(double x1,double y1,double x2,double y2){
                            	double rr=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
                            	return sqrt(rr);
                            	
                            }
                            
   //         int pr[2000010];
     //       int inv[2000010];
            
            int beki(int wa,int rr,int warukazu){
            	if(rr==0) return 1ll;
            	if(rr==1) return wa%warukazu;
            	if(rr%2==1) return (beki(wa,rr-1,warukazu)*wa)%warukazu;
            	int zx=beki(wa,rr/2,warukazu);
            	return (zx*zx)%warukazu;
            }
            /*
			int comb(int nn,int rr){
				int r=pr[nn]*inv[rr];
				r%=inf;
				r*=inv[nn-rr];
				r%=inf;
				return r;
			}
            
            void gya(int ert){
            	pr[0]=1;
            	for(int i=1;i<ert;i++){
            		pr[i]=(pr[i-1]*i)%inf;
            	}
            	for(int i=0;i<ert;i++) inv[i]=beki(pr[i],inf-2,inf);
            	
            }
             */
			//priority_queue<pa3,vector<pa3>,greater<pa3>> pq;            
             //sort(ve.begin(),ve.end(),greater<int>());
                                     //----------------kokomade tenpure------------
unsigned int randxor()
{
    static unsigned int x=123456789,y=362436069,z=521288629,w=88675123;
    unsigned int t;
    t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}

int mask=(1<<8)-1;
int ban[1010][1010]={0};
map<int,int> ma[2][1010];
  signed main(){
  	              cin.tie(0);
    		ios::sync_with_stdio(false);

  	int n,m;
  	cin>>n>>m;
  	
  	for(int i=1;i<=n;i++){
  		string s;
  		
  		cin>>s;
  		s="2"+s;
  		for(int j=1;j<=m;j++)if(s[j]!='.')ban[i][j]=s[j]-'0';
  	}

  	ma[1][1][ban[2][2]?1:0]=0;
  	  	
  	for(int i=1;i<=n;i++){
  		for(int j=1;j<=m;j++)ma[1^(i&1)][j].clear();
  		
  		for(int j=1;j<=m;j++){
  		if(i==n && j==m) break;
  		
  		for(auto it=ma[i&1][j].begin();it!=ma[i&1][j].end();it++){
  			if(i!=n){
  				int B=it->first;
  				int val=it->second;
  		//		cout<<i<<" "<<j<<"   "<<bitset<9>(B)<<" "<<val<<endl;
  				B=B<<3;
  				B&=mask;
  				if(ban[i+2][j-1])B|=4;
  				if(ban[i+2][j])B|=2;
  				if(ban[i+2][j+1])B|=1;
  				
  				if(B&(1<<4))val+=ban[i+1][j],B^=(1<<4);
  				vector<pa> ve;
  				if(B&(1<<1))B^=(1<<1),ve.pb(mp(1,ban[i+2][j]));
  				if(B&(1<<3))B^=(1<<3),ve.pb(mp(3,ban[i+1][j+1]));
  				if(B&(1<<5))B^=(1<<5),ve.pb(mp(5,ban[i+1][j-1]));
  				if(B&(1<<7))B^=(1<<7),ve.pb(mp(7,ban[i][j]));
  				if(ve.size()>1){
  					int l=ve.size();
  					int wa=0;
  					for(auto v:ve)wa+=v.second;
  					for(auto v:ve){
  						int B2=(B|(1<<v.first));
  						int val2=val+wa-v.second;
  						if(ma[1^(i&1)][j].find(B2)==ma[1^(i&1)][j].end()) ma[1^(i&1)][j][B2]=val2;
  						else ma[1^(i&1)][j][B2]=min(ma[1^(i&1)][j][B2],val2);
  					}
  				}
  				else{
  					if(ve.size())B|=(1<<ve[0].first);
  					if(ma[1^(i&1)][j].find(B)==ma[1^(i&1)][j].end()) ma[1^(i&1)][j][B]=val;
  					else ma[1^(i&1)][j][B]=min(ma[1^(i&1)][j][B],val);
  				}
  			}
  			if(j!=m){
  				int B=it->first;
  				int val=it->second;
  				B=B<<1;
  				B&=mask;
  				if(B&1)B^=1;
  				if(B&8)B^=8;
  				if(B&64)B^=64;
  				
  				if(ban[i-1][j+2])B|=64;
  				if(ban[i][j+2])B|=8;
  				if(ban[i+1][j+2])B|=1;
  				
  				if(B&(1<<4))val+=ban[i][j+1],B^=(1<<4);
  				vector<pa> ve;
  				if(B&(1<<1))B^=(1<<1),ve.pb(mp(1,ban[i+1][j+1]));
  				if(B&(1<<3))B^=(1<<3),ve.pb(mp(3,ban[i][j+2]));
  				if(B&(1<<5))B^=(1<<5),ve.pb(mp(5,ban[i][j]));
  				if(B&(1<<7))B^=(1<<7),ve.pb(mp(7,ban[i-1][j+1]));
  			//	if(i==1 && j==1)cout<<ve.size()<<endl;
  				if(ve.size()>1){
  					int l=ve.size();
  					int wa=0;
  					for(auto v:ve)wa+=v.second;
  					for(auto v:ve){
  						int B2=(B|(1<<v.first));
  						int val2=val+wa-v.second;
  						if(ma[i&1][j+1].find(B2)==ma[i&1][j+1].end()) ma[i&1][j+1][B2]=val2;
  						else ma[i&1][j+1][B2]=min(ma[i&1][j+1][B2],val2);
  					}
  				}
  				else{
  					if(ve.size())B|=(1<<ve[0].first);
  					if(ma[i&1][j+1].find(B)==ma[i&1][j+1].end()) ma[i&1][j+1][B]=val;
  					else ma[i&1][j+1][B]=min(ma[i&1][j+1][B],val);
  				}
  			}
  		}
  		}
  	}
  	
  	int lasans=inf;
  	for(auto it=ma[n&1][m].begin();it!=ma[n&1][m].end();it++)lasans=min(lasans,it->second);
  	cout<<lasans<<endl;
  	return 0;
                }