#include <iostream>
#include <utility>
#include <tuple>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <functional>
#include <climits>
#include <numeric>
#include <queue>
#include <cmath>
#include <iomanip>
#include <array>
#include <string>
#include <stack>
#include <cassert>
#include <memory>

template<typename T>
bool contains(const std::vector<T>& list, const T& target) {
	return std::find(list.begin(), list.end(), target) != list.end();
}
template<typename T, int C>
bool contains(const std::array<T, C>& array, const T& target) {
	return std::find(array.begin(), array.end(), target) != array.end();
}
struct Coordinate {
	int x{ 0 }, y{ 0 };
	constexpr Coordinate operator+(const Coordinate& that) const {
		return Coordinate{ x + that.x, y + that.y };
	}
	constexpr bool operator==(const Coordinate& that) const {
		return x == that.x && y == that.y;
	}
	constexpr Coordinate operator-(const Coordinate& that) const {
		return Coordinate{ x - that.x, y - that.y };
	}
	Coordinate& operator+=(const Coordinate& that) {
		x += that.x; y += that.y;
		return *this;
	}
};
constexpr std::array<Coordinate, 4> relative{ Coordinate{1, -1}, Coordinate{1, 0}, Coordinate{0, 1}, Coordinate{-1, 1} };
constexpr std::array<Coordinate, 2> next{ Coordinate{1, 0}, Coordinate{0, 1} };
constexpr std::array<Coordinate, 4> neighbor{ Coordinate{1, 0}, Coordinate{-1, 0}, Coordinate{0, 1}, Coordinate{0, -1} };

struct State {
	int pattern{ 0 };
	std::vector<Coordinate> bought() const {
		std::vector<Coordinate> result;
		for (auto i = 0; i < 4; ++i) {
			if (((1 << i) & pattern) != 0) {
				result.push_back(relative[i]);
			}
		}
		return result;
	}
	State() {}
	State(const Coordinate position, const std::vector<Coordinate>& bought) {
		for (auto i = 0; i < 4; ++i) {
			if (contains(bought, position + relative[i])) {
				pattern += 1 << i;
			}
		}
	}
};
struct Tuple {
	State state;
	Coordinate position;
	int cost;
};
template<typename T>
std::vector<T> operator+(const std::vector<T>& a, const std::vector<T>& b) {
	std::vector<T> result; result.resize(a.size() + b.size());
	for (const auto& v : a) result.push_back(v);
	for (const auto& v : b) result.push_back(v);
	return result;
}
std::vector<Tuple> next_state(const std::vector<std::vector<int>>& map, const Tuple tuple) {
	auto bought = tuple.state.bought(); for (auto& b : bought) b += tuple.position;
	std::vector<Tuple> result;
	for (const auto &dp : next) {
		const auto next = dp + tuple.position;
		if (0 > next.y || next.y >= map.size() || 0 > next.x || next.x >= map[next.y].size()) continue;
		std::vector<Coordinate> shop;
		int cost{ contains(bought, next) ? 0 : map[next.y][next.x] };
		for (const auto &np : neighbor) {
			const auto s = next + np;
			if (0 > s.y || s.y >= map.size() || 0 > s.x || s.x >= map[s.y].size()) continue;
			if (s == tuple.position || map[s.y][s.x] == 0 || contains(bought, s)) continue;
			shop.push_back(s);
			cost += map[s.y][s.x];
		}
		cost += tuple.cost;
		const auto last_state = State(next, bought + shop);
		result.push_back(Tuple{ last_state, next, cost });
		for (const auto np: neighbor) {
			const auto sp = next + np;
			if (!contains(shop, sp)) continue;
			auto ri = std::distance(relative.begin(), std::find(relative.begin(), relative.end(), np));
			auto last = last_state;
			if (ri < 4) {
				last.pattern -= 1 << ri;
			}
			result.push_back(Tuple{ last, next, cost - map[sp.y][sp.x] });
		}
	}
	return result;
}

int main() {
	int height, width; std::cin >> height >> width;
	std::vector<std::vector<int>> map(height, std::vector<int>(width));
	for (auto i = 0; i < height; ++i) {
		std::string str; std::cin >> str;
		for (auto j = 0; j < width; ++j) {
			switch (str[j]) {
			case '.': map[i][j] = 0; break;
			default: map[i][j] = str[j] - '0';
			}
		}
	}
	std::vector<std::vector<std::vector<int>>> min_cost(height, std::vector<std::vector<int>>(width, std::vector<int>(1 << 4, INT_MAX)));
	const auto comparator = [](const Tuple& a, const Tuple& b) {return a.cost > b.cost; };
	std::priority_queue<Tuple, std::vector<Tuple>, decltype(comparator)> queue(comparator);
	min_cost[0][0][0] = 0;
	queue.push(Tuple{ State(), Coordinate(), 0 });
	while (!queue.empty()) {
		auto top = queue.top(); queue.pop();
		if (min_cost[top.position.y][top.position.x][top.state.pattern] != top.cost) continue;
		if (top.position == Coordinate{ width - 1, height - 1 }) break;
		for (auto next : next_state(map, top)) {
			if (min_cost[next.position.y][next.position.x][next.state.pattern] > next.cost) {
				min_cost[next.position.y][next.position.x][next.state.pattern] = next.cost;
				queue.push(next);
			}
		}
	}
	std::cout << *std::min_element(min_cost.back().back().begin(), min_cost.back().back().end()) << std::endl;
}


Measured memory_bytes: 109572