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>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


//到着時の状態
#define Right_North 0
#define North 1
#define Here 2
#define Left 3
#define Left_South 4

//あるマスで調べる状態
#define UE 0
#define HIDARI 1
#define KOKO 2
#define MIGI 3
#define SHITA 4

char input[1000][1001];
int POW[6];
int table[1002][1002];
int min_cost[1002][1002][32];

int H,W;

int main(){

	for(int i = 0; i < 6; i++)POW[i] = pow(2,i);

	scanf("%d %d",&H,&W);

	for(int row = 0; row < H; row++){
		scanf("%s",input[row]);
	}

	//ダミーセルを用意
	for(int col = 0; col <= W+1; col++){
		table[0][col] = 0;
		table[H+1][col] = 0;
	}
	for(int row = 0; row <= H+1; row++){
		table[row][0] = 0;
		table[row][W+1] = 0;
	}

	//マップを転記
	for(int row = 0; row < H; row++){
		for(int col = 0; col < W; col++){
			if(input[row][col] == '.'){
				table[row+1][col+1] = 0;
			}else{
				table[row+1][col+1] = input[row][col]-'0';
			}
		}
	}

	for(int row = 1; row <= H; row++){
		for(int col = 1; col <= W; col++){
			for(int state = 0; state < 32; state++){
				min_cost[row][col][state] = BIG_NUM;
			}
		}
	}

	/*
	 * min_cost[row][col][隣接5箇所の数字を取得したか] = 最小コスト
	 * stateのビット:位置ビットの屋台の菓子を既に食べたか
	 *
	 */
	min_cost[1][1][0] = 0;
	int add_sum,add_loc,removed_add,removed_loc;
	int next_state;
	bool FLG;

	for(int row = 1; row <= H; row++){
		for(int col = 1; col <= W; col++){
			for(int state = 0; state < 32; state++){
				if(min_cost[row][col][state] == BIG_NUM)continue;

				//上下左右+今いる地点で、未加算の数字を調べる
				add_sum = 0,add_loc = 0;

				//上
				if((state & (1 << North)) == 0 && table[row-1][col] != 0){ //上が未加算で、かつ0でない
					add_sum += table[row-1][col];
					add_loc += POW[UE];
				}
				//左
				if((state & (1 << Left)) == 0 && table[row][col-1] != 0){
					add_sum += table[row][col-1];
					add_loc += POW[HIDARI];
				}
				//今いる場所
				if((state & (1 << Here)) == 0 && table[row][col] != 0){
					add_sum += table[row][col];
					add_loc += POW[KOKO];
				}
				//右
				if(table[row][col+1] != 0){
					add_sum += table[row][col+1];
					add_loc += POW[MIGI];
				}
				//下
				if(table[row+1][col] != 0){
					add_sum += table[row+1][col];
					add_loc += POW[SHITA];
				}

				if(add_loc == 0){ //数字を除く必要がない場合

					//右に進む
					next_state = 0;
					if(state & (1 << Right_North)){ //右上→上になる
						next_state += POW[North];
					}
					//今いる場所→左になる
					next_state += POW[Left]; //今いる場所は加算済み、または0、よって右のマスは今のマスを見る必要はない

					//右→「今いる場所になる」
					next_state += POW[Here]; //★add_loc == 0により

					//下は左下になる
					next_state += POW[Left_South]; //★add_loc == 0なので、table[row][col+1]は、新しい左下を無視して良いということ!
					min_cost[row][col+1][next_state] = min(min_cost[row][col+1][next_state],min_cost[row][col][state]);

					//下に進む
					next_state = 0;
					//今いる場所→上になる
					next_state += POW[North];

					if(state & (1 << Left_South)){ //左下→下になる
						next_state += POW[Left];
					}
					//右は右上になる
					next_state += POW[Right_North]; //★add_loc == 0のため
					//下は「今いる場所」になる
					next_state += POW[Here]; //★add_loc == 0のため、無条件で良い

					min_cost[row+1][col][next_state] = min(min_cost[row+1][col][next_state],min_cost[row][col][state]);
					continue;
				}

				//数字を除く必要がある場合

				for(int remove_loc = 0; remove_loc <= 4; remove_loc++){
					if(remove_loc == 2){

						if(add_loc == POW[KOKO]){ //★★今いる場所だけを加算した場合★★

							//右に進む
							next_state = 0;
							if(state & (1 << Right_North)){ //右上→上になる
								next_state += POW[North];
							}
							//今いる場所→左になる
							next_state += POW[Left]; //今いる場所は加算済み、または0、よって右のマスは今のマスを見る必要はない

							//右→「今いる場所になる」
							next_state += POW[Here]; //★add_loc == POW[KOKO]により

							//下は左下になる
							next_state += POW[Left_South]; //★add_loc == POW[KOKO]なので、table[row][col+1]は、新しい左下を無視して良いということ!
							min_cost[row][col+1][next_state] = min(min_cost[row][col+1][next_state],min_cost[row][col][state]+table[row][col]);

							//下に進む
							next_state = 0;
							//今いる場所→上になる
							next_state += POW[North];

							if(state & (1 << Left_South)){ //左下→下になる
								next_state += POW[Left];
							}
							//右は右上になる
							next_state += POW[Right_North]; //★add_loc == POW[KOKO]のため
							//下は「今いる場所」になる
							next_state += POW[Here]; //★add_loc == POW[KOKO]のため、無条件で良い

							min_cost[row+1][col][next_state] = min(min_cost[row+1][col][next_state],min_cost[row][col][state]+table[row][col]);

						}
						continue; //今いる場所は除けない
					}

					FLG = false;

					switch(remove_loc){
					case 0: //上
						if(add_loc & (1 << UE)){
							FLG = true;
							removed_add = add_sum-table[row-1][col];
							removed_loc = UE;
						}
						break;
					case 1: //左
						if(add_loc & (1 << HIDARI)){
							FLG = true;
							removed_add = add_sum-table[row][col-1];
							removed_loc = HIDARI;
						}
						break;
					case 3: //右
						if(add_loc & (1 << MIGI)){
							FLG = true;
							removed_add = add_sum-table[row][col+1];
							removed_loc = MIGI;
						}
						break;
					case 4: //下
						if(add_loc & (1 << SHITA)){
							FLG = true;
							removed_add = add_sum-table[row+1][col];
							removed_loc = SHITA;
						}
						break;
					}
					if(!FLG)continue;

					//右に進む
					next_state = 0;
					if(state & (1 << Right_North)){ //右上→上になる
						next_state += POW[North];
					}
					//今いる場所→左になる
					next_state += POW[Left]; //table[row][col+1]から見れば、仮に左のマスから来たなら、table[row][col]は加算不要なはず(今いるセルは除けないし、0なら無視して良い)

					//右→今いる場所になる
					if(removed_loc != MIGI && (add_loc & (1 << MIGI)) != 0){ //右は除外マスでなく、かつ加算されている
						next_state += POW[Here]; //加算済とする
					}

					//下→左下になる
					if(removed_loc != SHITA && (add_loc & (1 << SHITA)) != 0){ //下は除外マスでなく、かつ加算されている
						next_state += POW[Left_South]; //加算済とする
					}
					min_cost[row][col+1][next_state] = min(min_cost[row][col+1][next_state],min_cost[row][col][state]+removed_add);

					//下に進む
					next_state = 0;
					//今いる場所→上になる
					next_state += POW[North]; //右に進む場合と同様の理由で、無条件で良し

					if(state & (1 << Left_South)){ //左下→下になる
						next_state += POW[Left];
					}
					//右は右上になる
					if(removed_loc != MIGI && (add_loc & (1 << MIGI)) != 0){ //右は除外マスでなく、かつ加算されている
						next_state += POW[Right_North]; //加算済とする
					}
					//下は今いる場所になる
					if(removed_loc != SHITA && (add_loc & (1 << SHITA)) != 0){ //右は除外マスでなく、かつ加算されている
						next_state += POW[Here]; //加算済とする
					}
					min_cost[row+1][col][next_state] = min(min_cost[row+1][col][next_state],min_cost[row][col][state]+removed_add);
				}
			}
		}
	}

	int ans = BIG_NUM;
	for(int state = 0; state < 32; state++){
		ans = min(ans,min_cost[H][W][state]);
	}

	printf("%d\n",ans);

	return 0;
}