#include <algorithm>
#include <array>
#include <ios>
#include <iostream>
#include <numeric>
#include <string>
#include <utility>
#include <vector>
template <typename F>
class YCombinator {
private:
const F f = nullptr;
public:
explicit YCombinator(F&& f) : f(f) {}
template <typename... Ts>
decltype(auto) operator()(Ts&&... arguments) const {
return f(*this, std::forward<Ts>(arguments)...);
}
};
template <typename F>
YCombinator(F) -> YCombinator<F>;
constexpr auto dir_1 = std::array<int, 4>({1, 0, -1, 0});
constexpr auto dir_2 = std::array<int, 4>({0, 1, 0, -1});
auto solve() {
auto r = 0;
auto s = 0;
std::cin >> r >> s;
auto amts = std::vector<std::string>(r);
for (auto& x : amts) {
std::cin >> x;
}
auto sums = std::vector<std::vector<int>>(s, std::vector<int>(s + 1));
auto vis = std::vector<std::vector<bool>>(r, std::vector<bool>(s));
for (auto i = 0; i < r; ++i) {
for (auto j = 0; j < s; ++j) {
const auto canVisit = [&](int row, int col) {
return (
row >= 0 && row < r && col >= 0 && col < s && !vis[row][col] &&
amts[row][col] != '.'
);
};
if (!canVisit(i, j)) {
continue;
}
auto col_mn = s;
auto col_mx = -1;
auto sum = 0;
YCombinator(
[&](auto self, int row, int col) -> void {
sum += amts[row][col] - '0';
vis[row][col] = true;
col_mn = std::min(col_mn, col);
col_mx = std::max(col_mx, col);
for (auto i = 0; i < 4; ++i) {
const auto new_col = col + dir_1[i];
const auto new_row = row + dir_2[i];
if (canVisit(new_row, new_col)) {
self(new_row, new_col);
}
}
}
)(i, j);
sums[col_mn][col_mn] += sum;
sums[col_mn][col_mx + 1] -= sum;
}
}
for (auto& x : sums) {
std::partial_sum(x.begin(), x.end(), x.begin());
}
auto dp = std::vector<int>(s + 1, -1);
dp[0] = 0;
for (auto i = 1; i <= s; ++i) {
auto new_dp = std::vector<int>(s + 1, -1);
YCombinator(
[&](auto self, int idx_l, int idx_r, int opt_mn, int opt_mx) -> void {
const auto idx_m = (idx_l + idx_r) >> 1;
auto opt = opt_mn;
auto sum = 0;
for (auto i = idx_m; i > opt_mx; --i) {
sum += sums[i - 1][idx_m - 1];
}
for (auto i = std::min(opt_mx, idx_m); i >= opt_mn; --i) {
sum += sums[i - 1][idx_m - 1];
if (dp[i - 1] == -1) {
continue;
}
const auto val = dp[i - 1] + sum;
if (val < new_dp[idx_m] && new_dp[idx_m] != -1) {
continue;
}
new_dp[idx_m] = val;
opt = i;
}
if (idx_l < idx_m) {
self(idx_l, idx_m - 1, opt_mn, opt);
}
if (idx_r > idx_m) {
self(idx_m + 1, idx_r, opt, opt_mx);
}
}
)(1, s, 1, s);
dp = new_dp;
std::cout << *std::max_element(dp.begin(), dp.end()) << '\n';
}
}
auto main() -> int {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
return 0;
}
