code = """

# distutils: language=c++
# distutils: include_dirs=[/home/USERNAME/.local/lib/python3.8/site-packages/numpy/core/include, /opt/atcoder-stl]
# cython: boundscheck=False
# cython: wraparound=False

from libcpp.utility cimport pair
from libcpp.string cimport string
from libcpp.vector cimport vector
from libc.stdio cimport getchar, printf
cpdef inline vector[int] ReadInt(int n):
    cdef int b, c
    cdef vector[int] *v = new vector[int]()
    for i in range(n):
        c = 0
        while 1:
            b = getchar() - 48
            if b < 0: break
            c = c * 10 + b
        v.push_back(c)
    return v[0]

cpdef inline vector[string] Read(int n):
    cdef char c
    cdef vector[string] *vs = new vector[string]()
    cdef string *s
    for i in range(n):
        s = new string()
        while 1:
            c = getchar()
            if c<=32: break
            s.push_back(c)
        vs.push_back(s[0])
    return vs[0]

cpdef inline void PrintLongN(vector[long] l):
    cdef int n = l.size()
    for i in range(n): printf("%ld\\n", l[i])

cpdef inline void PrintLong(vector[long] l):
    cdef int n = l.size()
    for i in range(n): printf("%ld ", l[i])
cdef extern from *:
    ctypedef long long ll "long long"

cdef extern from "<atcoder/mincostflow>" namespace "atcoder":
    cdef cppclass mcf_graph[Cap, Cost]:
        mcf_graph(int n)
        int add_edge(int fr, int to, Cap cap, Cost cost)
        pair[Cap, Cost] flow(int s, int t)
        pair[Cap, Cost] flow(int s, int t, Cap flow_limit)
        vector[pair[Cap, Cost]] slope(int s, int t)
        vector[pair[Cap, Cost]] slope(int s, int t, Cap flow_limit)
        cppclass edge:
            int frm 'from'
            int to
            Cap cap
            Cap flow
            Cost cost
            edge(edge &e)
        edge get_edge(int i)
        vector[edge] edges()

cdef class McfGraph:
    cdef mcf_graph[int, ll] *_thisptr
    def __cinit__(self, int n):
        self._thisptr = new mcf_graph[int, ll](n)
    cpdef int add_edge(self, int fr, int to, int cap, ll cost):
        return self._thisptr.add_edge(fr, to, cap, cost)
    cpdef pair[int, ll] flow(self, int s, int t):
        return self._thisptr.flow(s, t)
    cpdef pair[int, ll] flow_with_limit(self, int s, int t, int flow_limit):
        return self._thisptr.flow(s, t, flow_limit)
    cpdef vector[pair[int, ll]] slope(self, int s, int t):
        return self._thisptr.slope(s, t)
    cpdef vector[pair[int, ll]] slope_with_limit(self, int s, int t, int flow_limit):
        return self._thisptr.slope(s, t, flow_limit)

    cpdef pair[vector[int], ll] get_edge(self, int i):
        cdef mcf_graph[int, ll].edge *e = new mcf_graph[int, ll].edge(self._thisptr.get_edge(i))
        cdef pair[vector[int], ll] *ret_e = new pair[vector[int], ll]()
        ret_e.first.push_back(e.frm)
        ret_e.first.push_back(e.to)
        ret_e.first.push_back(e.cap)
        ret_e.first.push_back(e.flow)
        ret_e.second = e.cost
        return ret_e[0]

    cpdef vector[pair[vector[int], ll]] edges(self):
        cdef vector[mcf_graph[int, ll].edge] es = self._thisptr.edges()
        cdef vector[pair[vector[int], ll]] *ret_es = new vector[pair[vector[int], ll]](es.size())
        for i in range(es.size()):
            ret_es.at(i).first.push_back(es.at(i).frm)
            ret_es.at(i).first.push_back(es.at(i).to)
            ret_es.at(i).first.push_back(es.at(i).cap)
            ret_es.at(i).first.push_back(es.at(i).flow)
            ret_es.at(i).second = es.at(i).cost
        return ret_es[0]
"""


import os, sys, getpass

if sys.argv[-1] == 'ONLINE_JUDGE':
    code = code.replace("USERNAME", getpass.getuser())
    open('atcoder.pyx','w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')
    sys.exit(0)


from atcoder import McfGraph, ReadInt, Read

N, M = ReadInt(2)
S = [r.decode() for r in Read(N)]

mg = McfGraph(N*M+2)
s = N*M
t = N*M+1
BIG = 1000

def I(i,j):
    return i*M+j

initial = 0

for i in range(N):
    for j in range(M):
        x = I(i,j)
        if S[i][j]=="o":
            mg.add_edge(s,x,1,0)
            initial+=BIG-i-j
        if S[i][j]!="#":
            mg.add_edge(x,t,1,BIG-i-j)
        if i<N-1:
            if S[i][j]!="#" and S[i+1][j]!="#":
                mg.add_edge(x,I(i+1,j),BIG,0)
        if j<M-1:
            if S[i][j]!="#" and S[i][j+1]!="#":
                mg.add_edge(x,I(i,j+1),BIG,0)

n, score = mg.flow(s,t)
print(initial-score)

Measured memory_bytes: 11464