#include <bits/stdc++.h>
#define st first
#define nd second
using lint = int64_t;
constexpr int mod = int(1e9) + 7;
constexpr int inf = 0x3f3f3f3f;
constexpr int ninf = 0xcfcfcfcf;
constexpr lint linf = 0x3f3f3f3f3f3f3f3f;
const long double pi = acosl(-1.0);
// Returns -1 if a < b, 0 if a = b and 1 if a > b.
int cmp_double(double a, double b = 0, double eps = 1e-9) {
return a + eps > b ? b + eps > a ? 0 : 1 : -1;
}
using namespace std;
struct DP { // Modify at will:
vector<vector<int>>cost;
vector<int> old, cur;
DP(const vector<vector<int>>&_cost, int n): cost(_cost), old(n, inf), cur(n, inf) {}
int lo(int ind) { return 0; }
int hi(int ind) { return ind; }
lint f(int ind, int k) { return old[k] + cost[k][ind]; }
void store(int ind, int k, lint v) { cur[ind] = (int)v; }
void rec(int L, int R, int LO, int HI) {
if (L >= R) return;
int mid = (L + R) >> 1;
pair<lint, int> best(LLONG_MAX, LO);
for(int k = max(LO,lo(mid)); k <= min(HI,hi(mid)); ++k)
best = min(best, make_pair(f(mid, k), k));
store(mid, best.second, best.first);
rec(L, mid, LO, best.second);
rec(mid+1, R, best.second, HI);
}
void solve(int L, int R) { rec(L, R, INT_MIN, INT_MAX); }
};
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
/*
ifstream cin;
cin.open("cbarn.in");
ofstream cout;
cout.open("cbarn.out");
*/
int n, m;
cin>>n>>m;
vector<string>s(n);
for(int i=0;i<n;i++) cin>>s[i];
vector<vector<bool>>vis(n, vector<bool>(m));
vector<int>sum, l, r;
int comp = 0;
vector<pair<int, int>>dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
auto dfs = [&](auto& self, int x, int y)->void{
vis[x][y] = 1;
l[comp] = min(l[comp], y);
r[comp] = max(r[comp], y);
sum[comp] += s[x][y] - '0';
for(auto [a, b] : dir){
int nx = x + a, ny = y + b;
if(nx < 0 || nx >= n || ny < 0 || ny >= m || vis[nx][ny] || s[nx][ny] == '.') continue;
self(self, nx, ny);
}
};
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(!vis[i][j] && s[i][j] != '.'){
sum.push_back(0);
l.push_back(j);
r.push_back(j);
dfs(dfs, i, j);
comp++;
}
}
}
vector<vector<int>>cost(m+1, vector<int>(m+1)), aux = cost;
for(int i=0;i<comp;i++){
for(int j=l[i];j<=r[i];j++) aux[l[i] + 1][j + 1] -= sum[i];
}
for(int i=m-1;i>=0;i--){
for(int j=i+1;j<=m;j++){
cost[i][j] = cost[i+1][j] + aux[i+1][j];
}
}
DP dp(cost, m+1);
dp.old[0] = 0;
for(int i=0;i<m;i++){
dp.rec(0, m+1, 0, m+1);
swap(dp.old, dp.cur);
int ans = inf;
for(int j=1;j<=m;j++) ans = min(ans, dp.old[j]);
cout<<-ans<<"\n";
}
return 0;
}
/*
[ ]Leu o problema certo???
[ ]Ver se precisa de long long
[ ]Viu o limite dos fors (é n? é m?)
[ ]Tamanho do vetor, será que é 2e5 em vez de 1e5??
[ ]Testar sample
[ ]Testar casos de borda
[ ]1LL no 1LL << i
[ ]Testar mod (é 1e9+7, mesmo?, será que o mod não ficou negativo?)
*/
