//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4", "avx")

#ifdef __APPLE__
# include <iostream>
# include <cmath>
# include <algorithm>
# include <stdio.h>
# include <cstdint>
# include <cstring>
# include <string>
# include <cstdlib>
# include <vector>
# include <bitset>
# include <map>
# include <queue>
# include <ctime>
# include <stack>
# include <set>
# include <list>
# include <random>
# include <deque>
# include <functional>
# include <iomanip>
# include <sstream>
# include <fstream>
# include <complex>
# include <numeric>
# include <immintrin.h>
# include <cassert>
# include <array>
# include <tuple>
# include <unordered_map>
# include <unordered_set>
# include <thread>
#else
# include <bits/stdc++.h>
#endif

#define F first
#define S second
#define MP make_pair
#define PB push_back

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

const int max_n = 50+5, inf = 1000111222;

int id[max_n][max_n];
char a[max_n][max_n];

struct edge
{
    int to,flow,cost;
};

vector<edge> edges;
vector<int> reb[max_n*max_n+10];
int dist[max_n*max_n+10];
int p[max_n*max_n+10];
pii pred[max_n*max_n+10];

void add_edge(int u,int v,int flow,int cost)
{
    reb[u].pb(edges.size());
    edges.pb(edge{v,flow,cost});

    reb[v].pb(edges.size());
    edges.pb(edge{u,0,-cost});
}

pii min_cost_max_flow(int s,int t)
{
    pii res;

    while (1){
//        p[t]=inf;
//        for (auto i:edges){
//            if (i.to == t){
//                p[t]=min(p[t],i.cost);
//            }
//        }

//        cout<<"min_cost_max_flow goes"<<"\n";
        set<pii> q;
        for (int i=s;i<=t;i++){
            dist[i]=inf;
            if (i==s){
                dist[i]=0;
            }
            q.insert(mp(dist[i],i));
        }

        while (!q.empty()){
            pii now=*q.begin();
            q.erase(q.begin());
            if (dist[now.sec]==inf){
                break;
            }
            for (auto wh_edge:reb[now.sec]){
                int to=edges[wh_edge].to;
                int flow=edges[wh_edge].flow;
                int cost=edges[wh_edge].cost;

                if (flow!=0 && dist[to] > dist[now.sec] + (cost + p[to] - p[now.sec])){
                    q.erase(mp(dist[to],to));
                    dist[to] = dist[now.sec] + (cost + p[to] - p[now.sec]);
                    q.insert(mp(dist[to],to));

                    pred[to]=mp(now.sec,wh_edge);
//                    cout<<"pred of "<<to<<" "<<"is "<<now.sec<<"\n";
                }
            }
        }

//        {
//            char wait;
//            cin>>wait;
//        }

        if (dist[t]==inf){
            return res;
        }

        // go_back

        int cur=t;
        int sum_cost=0;
        while (cur!=s){
//            cout<<"  cur :: "<<cur<<"\n";
            int pred_from=pred[cur].fir;
            int pred_edge=pred[cur].sec;
            sum_cost+=edges[pred_edge].cost;

            edges[pred_edge].flow--;
            edges[pred_edge^1].flow++;

            cur=pred_from;
        }

        res.fir++;
        res.sec+=sum_cost;

        for (int i=s;i<=t;i++){
            if (dist[i]!=inf){
                dist[i]+=p[i];
            }
        }

//        {
//            char wait;
//            cin>>wait;
//        }
    }
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    int n,m;
    cin>>n>>m;
    int s=0;
    int t=1;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            id[i][j] = t++;
            cin>>a[i][j];
        }
    }
    int sum_initial=0;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            if (a[i][j]=='o'){
                add_edge(s,id[i][j],1,0);
                sum_initial+=(i+j);
            }
        }
    }
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            if (a[i][j]!='#'){
                if (i+1<=n && a[i+1][j]!='#'){
                    add_edge(id[i][j],id[i+1][j],inf,0);
                }
                if (j+1<=m && a[i][j+1]!='#'){
                    add_edge(id[i][j],id[i][j+1],inf,0);
                }
            }
        }
    }
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            if (a[i][j]!='#'){
                add_edge(id[i][j],t,1,-(i+j));
            }
        }
    }
    cout<<-min_cost_max_flow(s,t).sec-sum_initial<<"\n";
}


Measured memory_bytes: 4028