Problem:


Score : 600 points

Problem Statement

There is a board with N rows and M columns.
The information of this board is represented by N strings S_1,S_2,\ldots,S_N.
Specifically, the state of the square at the i-th row from the top and the j-th column from the left is represented as follows:

S_{i,j}=. : the square is empty.

S_{i,j}=# : an obstacle is placed on the square.

S_{i,j}=o : a piece is placed on the square.

Yosupo repeats the following operation:

Choose a piece and move it to its right adjecent square or its down adjacent square.
Moving a piece to squares with another piece or an obstacle is prohibited.
Moving a piece out of the board is also prohibited.

Yosupo wants to perform the operation as many times as possible.
Find the maximum possible number of operations.

Constraints

1 \leq N \leq 50

1 \leq M \leq 50

S_i is a string of length M consisting of ., # and o.

1 \leq ( the number of pieces )\leq 100.
In other words, the number of pairs (i, j) that satisfy S_{i,j}=o is between 1 and 100, both inclusive.

Input

Input is given from Standard Input in the following format:

N M
S_1
S_2
\vdots
S_N

Output

Print the maximum possible number of operations in a line.

Sample Input 1

3 3
o..
...
o.#

Sample Output 1

4

Yosupo can perform operations 4 times as follows:

o..      .o.      ..o      ...      ...
...  ->  ...  ->  ...  ->  ..o  ->  ..o
o.#      o.#      o.#      o.#      .o#

Sample Input 2

9 10
.#....o#..
.#..#..##o
.....#o.##
.###.#o..o
#.#...##.#
..#..#.###
#o.....#..
....###..o
o.......o#

Sample Output 2

24



Sample input:
3 3
o..
...
o.#


Sample output:
4

Submission status: Accepted

Solution code:
# TODO: メモリリーク確認

code_mcf_graph = r"""
#define PY_SSIZE_T_CLEAN
#include <Python.h>
#include "structmember.h"

// 元のライブラリの private を剥がした

// >>> AtCoder >>>

#ifndef ATCODER_MINCOSTFLOW_HPP
#define ATCODER_MINCOSTFLOW_HPP 1

#include <algorithm>
#include <cassert>
#include <limits>
#include <queue>
#include <vector>

namespace atcoder {

template <class Cap, class Cost> struct mcf_graph {
  public:
    mcf_graph() {}
    mcf_graph(int n) : _n(n), g(n) {}

    int add_edge(int from, int to, Cap cap, Cost cost) {
        assert(0 <= from && from < _n);
        assert(0 <= to && to < _n);
        int m = int(pos.size());
        pos.push_back({from, int(g[from].size())});
        int from_id = int(g[from].size());
        int to_id = int(g[to].size());
        if (from == to) to_id++;
        g[from].push_back(_edge{to, to_id, cap, cost});
        g[to].push_back(_edge{from, from_id, 0, -cost});
        return m;
    }

    struct edge {
        int from, to;
        Cap cap, flow;
        Cost cost;
    };

    edge get_edge(int i) {
        int m = int(pos.size());
        assert(0 <= i && i < m);
        auto _e = g[pos[i].first][pos[i].second];
        auto _re = g[_e.to][_e.rev];
        return edge{
            pos[i].first, _e.to, _e.cap + _re.cap, _re.cap, _e.cost,
        };
    }
    std::vector<edge> edges() {
        int m = int(pos.size());
        std::vector<edge> result(m);
        for (int i = 0; i < m; i++) {
            result[i] = get_edge(i);
        }
        return result;
    }

    std::pair<Cap, Cost> flow(int s, int t) {
        return flow(s, t, std::numeric_limits<Cap>::max());
    }
    std::pair<Cap, Cost> flow(int s, int t, Cap flow_limit) {
        return slope(s, t, flow_limit).back();
    }
    std::vector<std::pair<Cap, Cost>> slope(int s, int t) {
        return slope(s, t, std::numeric_limits<Cap>::max());
    }
    std::vector<std::pair<Cap, Cost>> slope(int s, int t, Cap flow_limit) {
        assert(0 <= s && s < _n);
        assert(0 <= t && t < _n);
        assert(s != t);
        // variants (C = maxcost):
        // -(n-1)C <= dual[s] <= dual[i] <= dual[t] = 0
        // reduced cost (= e.cost + dual[e.from] - dual[e.to]) >= 0 for all edge
        std::vector<Cost> dual(_n, 0), dist(_n);
        std::vector<int> pv(_n), pe(_n);
        std::vector<bool> vis(_n);
        auto dual_ref = [&]() {
            std::fill(dist.begin(), dist.end(),
                      std::numeric_limits<Cost>::max());
            std::fill(pv.begin(), pv.end(), -1);
            std::fill(pe.begin(), pe.end(), -1);
            std::fill(vis.begin(), vis.end(), false);
            struct Q {
                Cost key;
                int to;
                bool operator<(Q r) const { return key > r.key; }
            };
            std::priority_queue<Q> que;
            dist[s] = 0;
            que.push(Q{0, s});
            while (!que.empty()) {
                int v = que.top().to;
                que.pop();
                if (vis[v]) continue;
                vis[v] = true;
                if (v == t) break;
                // dist[v] = shortest(s, v) + dual[s] - dual[v]
                // dist[v] >= 0 (all reduced cost are positive)
                // dist[v] <= (n-1)C
                for (int i = 0; i < int(g[v].size()); i++) {
                    auto e = g[v][i];
                    if (vis[e.to] || !e.cap) continue;
                    // |-dual[e.to] + dual[v]| <= (n-1)C
                    // cost <= C - -(n-1)C + 0 = nC
                    Cost cost = e.cost - dual[e.to] + dual[v];
                    if (dist[e.to] - dist[v] > cost) {
                        dist[e.to] = dist[v] + cost;
                        pv[e.to] = v;
                        pe[e.to] = i;
                        que.push(Q{dist[e.to], e.to});
                    }
                }
            }
            if (!vis[t]) {
                return false;
            }

            for (int v = 0; v < _n; v++) {
                if (!vis[v]) continue;
                // dual[v] = dual[v] - dist[t] + dist[v]
                //         = dual[v] - (shortest(s, t) + dual[s] - dual[t]) + (shortest(s, v) + dual[s] - dual[v])
                //         = - shortest(s, t) + dual[t] + shortest(s, v)
                //         = shortest(s, v) - shortest(s, t) >= 0 - (n-1)C
                dual[v] -= dist[t] - dist[v];
            }
            return true;
        };
        Cap flow = 0;
        Cost cost = 0, prev_cost_per_flow = -1;
        std::vector<std::pair<Cap, Cost>> result;
        result.push_back({flow, cost});
        while (flow < flow_limit) {
            if (!dual_ref()) break;
            Cap c = flow_limit - flow;
            for (int v = t; v != s; v = pv[v]) {
                c = std::min(c, g[pv[v]][pe[v]].cap);
            }
            for (int v = t; v != s; v = pv[v]) {
                auto& e = g[pv[v]][pe[v]];
                e.cap -= c;
                g[v][e.rev].cap += c;
            }
            Cost d = -dual[s];
            flow += c;
            cost += c * d;
            if (prev_cost_per_flow == d) {
                result.pop_back();
            }
            result.push_back({flow, cost});
            prev_cost_per_flow = d;
        }
        return result;
    }

//  private:
    int _n;

    struct _edge {
        int to, rev;
        Cap cap;
        Cost cost;
    };

    std::vector<std::pair<int, int>> pos;
    std::vector<std::vector<_edge>> g;
};

}  // namespace atcoder

#endif  // ATCODER_MINCOSTFLOW_HPP

// <<< AtCoder <<<

using namespace std;
using namespace atcoder;
#define PARSE_ARGS(types, ...) if(!PyArg_ParseTuple(args, types, __VA_ARGS__)) return NULL


struct MCFGraph{
    PyObject_HEAD
    mcf_graph<long long, long long>* graph;
};

struct MCFGraphEdge{
    PyObject_HEAD
    mcf_graph<long long, long long>::edge* edge;
};


extern PyTypeObject MCFGraphType;
extern PyTypeObject MCFGraphEdgeType;


// >>> MCFGraph definition >>>

static void MCFGraph_dealloc(MCFGraph* self){
    delete self->graph;
    Py_TYPE(self)->tp_free((PyObject*)self);
}
static PyObject* MCFGraph_new(PyTypeObject* type, PyObject* args, PyObject* kwds){
    return type->tp_alloc(type, 0);
}
static int MCFGraph_init(MCFGraph* self, PyObject* args){
    long n;
    if(!PyArg_ParseTuple(args, "l", &n)) return -1;
    if(n < 0 || n > (long)1e8){
        PyErr_Format(PyExc_IndexError,
            "constraint error in MCFGraph constructor (constraint: 0<=n<=1e8, got n=%d)", n);
        return -1;
    }
    self->graph = new mcf_graph<long long, long long>(n);
    return 0;
}
static PyObject* MCFGraph_add_edge(MCFGraph* self, PyObject* args){
    long from, to;
    long long cap, cost;
    PARSE_ARGS("llLL", &from, &to, &cap, &cost);
    if(from < 0 || from >= self->graph->_n || to < 0 || to >= self->graph->_n){
        PyErr_Format(PyExc_IndexError,
            "MCFGraph add_edge index out of range (n=%d, from=%d, to=%d)", self->graph->_n, from, to);
        return (PyObject*)NULL;
    }
    if(from == to){
        PyErr_Format(PyExc_IndexError, "got self-loop (from=%d, to=%d)", from, to);
        return (PyObject*)NULL;
    }
    if(cap < 0){
        PyErr_Format(PyExc_IndexError, "got negative cap (cap=%d)", cap);
        return (PyObject*)NULL;
    }
    if(cost < 0){
        PyErr_Format(PyExc_IndexError, "got negative cost (cap=%d)", cost);
        return (PyObject*)NULL;
    }
    const int res = self->graph->add_edge(from, to, cap, cost);
    return Py_BuildValue("l", res);
}
static PyObject* MCFGraph_flow(MCFGraph* self, PyObject* args){
    long s, t;
    long long flow_limit = numeric_limits<long long>::max();
    PARSE_ARGS("ll|L", &s, &t, &flow_limit);
    if(s < 0 || s >= self->graph->_n || t < 0 || t >= self->graph->_n){
        PyErr_Format(PyExc_IndexError,
            "MCFGraph flow index out of range (n=%d, s=%d, t=%d)", self->graph->_n, s, t);
        return (PyObject*)NULL;
    }
    if(s == t){
        PyErr_Format(PyExc_IndexError, "got s == t (s=%d, t=%d)", s, t);
        return (PyObject*)NULL;
    }
    const pair<long long, long long>& flow_cost = self->graph->flow(s, t, flow_limit);
    return Py_BuildValue("LL", flow_cost.first, flow_cost.second);
}
static PyObject* MCFGraph_slope(MCFGraph* self, PyObject* args){
    long s, t;
    long long flow_limit = numeric_limits<long long>::max();
    PARSE_ARGS("ll|L", &s, &t, &flow_limit);
    if(s < 0 || s >= self->graph->_n || t < 0 || t >= self->graph->_n){
        PyErr_Format(PyExc_IndexError,
            "MCFGraph slope index out of range (n=%d, s=%d, t=%d)", self->graph->_n, s, t);
        return (PyObject*)NULL;
    }
    if(s == t){
        PyErr_Format(PyExc_IndexError, "got s == t (s=%d, t=%d)", s, t);
        return (PyObject*)NULL;
    }
    const vector<pair<long long, long long>>& slope = self->graph->slope(s, t, flow_limit);
    const int siz = (int)slope.size();
    PyObject* list = PyList_New(siz);
    for(int i = 0; i < siz; i++){
        PyList_SET_ITEM(list, i, Py_BuildValue("LL", slope[i].first, slope[i].second));
    }
    return list;
}
static PyObject* MCFGraph_get_edge(MCFGraph* self, PyObject* args){
    long i;
    PARSE_ARGS("l", &i);
    const int m = (int)self->graph->pos.size();
    if(i < 0 || i >= m){
        PyErr_Format(PyExc_IndexError,
            "MCFGraph get_edge index out of range (m=%d, i=%d)", m, i);
        return (PyObject*)NULL;
    }
    MCFGraphEdge* edge = PyObject_NEW(MCFGraphEdge, &MCFGraphEdgeType);
    edge->edge = new mcf_graph<long long, long long>::edge(self->graph->get_edge(i));
    return (PyObject*)edge;
}
static PyObject* MCFGraph_edges(MCFGraph* self, PyObject* args){
    const auto& edges = self->graph->edges();
    const int m = (int)edges.size();
    PyObject* list = PyList_New(m);
    for(int i = 0; i < m; i++){
        MCFGraphEdge* edge = PyObject_NEW(MCFGraphEdge, &MCFGraphEdgeType);
        edge->edge = new mcf_graph<long long, long long>::edge(edges[i]);
        PyList_SET_ITEM(list, i, (PyObject*)edge);
    }
    return list;
}
static PyObject* MCFGraph_repr(PyObject* self){
    PyObject* edges = MCFGraph_edges((MCFGraph*)self, NULL);
    PyObject* res = PyUnicode_FromFormat("MCFGraph(%R)", edges);
    Py_DECREF(edges);
    return res;
}
static PyMethodDef MCFGraph_methods[] = {
    {"add_edge", (PyCFunction)MCFGraph_add_edge, METH_VARARGS, "Add edge"},
    {"flow", (PyCFunction)MCFGraph_flow, METH_VARARGS, "Flow"},
    {"slope", (PyCFunction)MCFGraph_slope, METH_VARARGS, "Slope"},
    {"get_edge", (PyCFunction)MCFGraph_get_edge, METH_VARARGS, "Get edge"},
    {"edges", (PyCFunction)MCFGraph_edges, METH_VARARGS, "Get edges"},
    {NULL}  /* Sentinel */
};
PyTypeObject MCFGraphType = {
    PyObject_HEAD_INIT(NULL)
    "atcoder.MCFGraph",                 /*tp_name*/
    sizeof(MCFGraph),                   /*tp_basicsize*/
    0,                                  /*tp_itemsize*/
    (destructor)MCFGraph_dealloc,       /*tp_dealloc*/
    0,                                  /*tp_print*/
    0,                                  /*tp_getattr*/
    0,                                  /*tp_setattr*/
    0,                                  /*reserved*/
    MCFGraph_repr,                      /*tp_repr*/
    0,                                  /*tp_as_number*/
    0,                                  /*tp_as_sequence*/
    0,                                  /*tp_as_mapping*/
    0,                                  /*tp_hash*/
    0,                                  /*tp_call*/
    0,                                  /*tp_str*/
    0,                                  /*tp_getattro*/
    0,                                  /*tp_setattro*/
    0,                                  /*tp_as_buffer*/
    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE, /*tp_flags*/
    0,                                  /*tp_doc*/
    0,                                  /*tp_traverse*/
    0,                                  /*tp_clear*/
    0,                                  /*tp_richcompare*/
    0,                                  /*tp_weaklistoffset*/
    0,                                  /*tp_iter*/
    0,                                  /*tp_iternext*/
    MCFGraph_methods,                   /*tp_methods*/
    0,                                  /*tp_members*/
    0,                                  /*tp_getset*/
    0,                                  /*tp_base*/
    0,                                  /*tp_dict*/
    0,                                  /*tp_descr_get*/
    0,                                  /*tp_descr_set*/
    0,                                  /*tp_dictoffset*/
    (initproc)MCFGraph_init,            /*tp_init*/
    0,                                  /*tp_alloc*/
    MCFGraph_new,                       /*tp_new*/
    0,                                  /*tp_free*/
    0,                                  /*tp_is_gc*/
    0,                                  /*tp_bases*/
    0,                                  /*tp_mro*/
    0,                                  /*tp_cache*/
    0,                                  /*tp_subclasses*/
    0,                                  /*tp_weaklist*/
    0,                                  /*tp_del*/
    0,                                  /*tp_version_tag*/
    0,                                  /*tp_finalize*/
};

// <<< MCFGraph definition <<<


// >>> MCFGraphEdge definition >>>

static void MCFGraphEdge_dealloc(MCFGraphEdge* self){
    delete self->edge;
    Py_TYPE(self)->tp_free((PyObject*)self);
}
static PyObject* MCFGraphEdge_new(PyTypeObject* type, PyObject* args, PyObject* kwds){
    return type->tp_alloc(type, 0);
}
static int MCFGraphEdge_init(MCFGraphEdge* self, PyObject* args){
    int from, to;
    long long cap, flow, cost;
    if(!PyArg_ParseTuple(args, "llLLL", &from, &to, &cap, &flow, &cost)) return -1;
    self->edge = new mcf_graph<long long, long long>::edge(mcf_graph<long long, long long>::edge{from, to, cap, flow, cost});
    return 0;
}
static PyObject* MCFGraphEdge_get_from(MCFGraphEdge* self, PyObject* args){
    return PyLong_FromLong(self->edge->from);
}
static PyObject* MCFGraphEdge_get_to(MCFGraphEdge* self, PyObject* args){
    return PyLong_FromLong(self->edge->to);
}
static PyObject* MCFGraphEdge_get_flow(MCFGraphEdge* self, PyObject* args){
    return PyLong_FromLongLong(self->edge->flow);
}
static PyObject* MCFGraphEdge_get_cap(MCFGraphEdge* self, PyObject* args){
    return PyLong_FromLongLong(self->edge->cap);
}
static PyObject* MCFGraphEdge_get_cost(MCFGraphEdge* self, PyObject* args){
    return PyLong_FromLongLong(self->edge->cost);
}
static PyObject* MCFGraphEdge_repr(PyObject* self){
    MCFGraphEdge* self_ = (MCFGraphEdge*)self;
    PyObject* res = PyUnicode_FromFormat("MCFGraphEdge(%2d -> %2d, %2lld / %2lld, cost = %2lld)",
        self_->edge->from, self_->edge->to, self_->edge->flow, self_->edge->cap, self_->edge->cost);
    return res;
}
PyGetSetDef MCFGraphEdge_getsets[] = {
    {"from_", (getter)MCFGraphEdge_get_from, NULL, NULL, NULL},
    {"to", (getter)MCFGraphEdge_get_to, NULL, NULL, NULL},
    {"flow", (getter)MCFGraphEdge_get_flow, NULL, NULL, NULL},
    {"cap", (getter)MCFGraphEdge_get_cap, NULL, NULL, NULL},
    {"cost", (getter)MCFGraphEdge_get_cost, NULL, NULL, NULL},
    {NULL}
};
PyTypeObject MCFGraphEdgeType = {
    PyObject_HEAD_INIT(NULL)
    "atcoder.MCFGraphEdge",             /*tp_name*/
    sizeof(MCFGraphEdge),               /*tp_basicsize*/
    0,                                  /*tp_itemsize*/
    (destructor)MCFGraphEdge_dealloc,   /*tp_dealloc*/
    0,                                  /*tp_print*/
    0,                                  /*tp_getattr*/
    0,                                  /*tp_setattr*/
    0,                                  /*reserved*/
    MCFGraphEdge_repr,                  /*tp_repr*/
    0,                                  /*tp_as_number*/
    0,                                  /*tp_as_sequence*/
    0,                                  /*tp_as_mapping*/
    0,                                  /*tp_hash*/
    0,                                  /*tp_call*/
    0,                                  /*tp_str*/
    0,                                  /*tp_getattro*/
    0,                                  /*tp_setattro*/
    0,                                  /*tp_as_buffer*/
    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE, /*tp_flags*/
    0,                                  /*tp_doc*/
    0,                                  /*tp_traverse*/
    0,                                  /*tp_clear*/
    0,                                  /*tp_richcompare*/
    0,                                  /*tp_weaklistoffset*/
    0,                                  /*tp_iter*/
    0,                                  /*tp_iternext*/
    0,                                  /*tp_methods*/
    0,                                  /*tp_members*/
    MCFGraphEdge_getsets,               /*tp_getset*/
    0,                                  /*tp_base*/
    0,                                  /*tp_dict*/
    0,                                  /*tp_descr_get*/
    0,                                  /*tp_descr_set*/
    0,                                  /*tp_dictoffset*/
    (initproc)MCFGraphEdge_init,        /*tp_init*/
    0,                                  /*tp_alloc*/
    MCFGraphEdge_new,                   /*tp_new*/
    0,                                  /*tp_free*/
    0,                                  /*tp_is_gc*/
    0,                                  /*tp_bases*/
    0,                                  /*tp_mro*/
    0,                                  /*tp_cache*/
    0,                                  /*tp_subclasses*/
    0,                                  /*tp_weaklist*/
    0,                                  /*tp_del*/
    0,                                  /*tp_version_tag*/
    0,                                  /*tp_finalize*/
};

// <<< MCFGraphEdge definition <<<


static PyModuleDef atcodermodule = {
    PyModuleDef_HEAD_INIT,
    "atcoder",
    NULL,
    -1,
};

PyMODINIT_FUNC PyInit_atcoder(void)
{
    PyObject* m;
    if(PyType_Ready(&MCFGraphType) < 0) return NULL;
    if(PyType_Ready(&MCFGraphEdgeType) < 0) return NULL;

    m = PyModule_Create(&atcodermodule);
    if(m == NULL) return NULL;

    Py_INCREF(&MCFGraphType);
    if (PyModule_AddObject(m, "MCFGraph", (PyObject*)&MCFGraphType) < 0) {
        Py_DECREF(&MCFGraphType);
        Py_DECREF(m);
        return NULL;
    }

    Py_INCREF(&MCFGraphEdgeType);
    if (PyModule_AddObject(m, "MCFGraphEdge", (PyObject*)&MCFGraphEdgeType) < 0) {
        Py_DECREF(&MCFGraphEdgeType);
        Py_DECREF(m);
        return NULL;
    }
    return m;
}
"""
code_mcf_graph_setup = r"""
from distutils.core import setup, Extension
module = Extension(
    "atcoder",
    sources=["mcf_graph.cpp"],
    extra_compile_args=["-O3", "-march=native", "-std=c++14"]
)
setup(
    name="atcoder-library",
    version="0.0.1",
    description="wrapper for atcoder library",
    ext_modules=[module]
)
"""

import os
import sys

if sys.argv[-1] == "ONLINE_JUDGE" or os.getcwd() != "/imojudge/sandbox":
    with open("mcf_graph.cpp", "w") as f:
        f.write(code_mcf_graph)
    with open("mcf_graph_setup.py", "w") as f:
        f.write(code_mcf_graph_setup)
    os.system(f"{sys.executable} mcf_graph_setup.py build_ext --inplace")

from atcoder import MCFGraph


N, M = map(int, input().split())
S = [input()+"#" for _ in range(N)] + ["#"*M]
g = MCFGraph(N*M+2)
s = N*M
t = s + 1
offset = 0
BIG = 10**9
for y in range(N):
    for x in range(M):
        i = y*M + x
        c = S[y][x]
        r = S[y][x+1]
        d = S[y+1][x]
        if c != "#":
            cost = BIG - y - x
            g.add_edge(i, t, 1, cost)
            if c == "o":
                g.add_edge(s, i, 1, 0)
                offset += cost
            if r != "#":
                g.add_edge(i, i+1, 100, 0)
            if d != "#":
                g.add_edge(i, i+M, 100, 0)
ans = offset - g.flow(s, t)[1]
print(ans)

Submission status: Accepted

Solution code:
code = r'''
# distutils: language=c++
# distutils: include_dirs=[/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include,/opt/atcoder-stl]
# cython: boundscheck=False
# cython: wraparound=False
from libcpp cimport bool
from libcpp.string cimport string
from libcpp.vector cimport vector
from libcpp.pair cimport pair
cdef extern from *:
    ctypedef int MOD '998244353'
    ctypedef long long ll 'long long'
#
cdef extern from '<atcoder/fenwicktree>' namespace 'atcoder':
    cdef cppclass fenwick_tree[T]:
        fenwick_tree(int n)
        void add(int p, T x)
        T sum(int l, int r)
cdef class fenwick_tree_:
    cdef fenwick_tree[int] *ptr
    def __cinit__(self, int n): self.ptr = new fenwick_tree[int](n)  
    def __dealloc__(self): del self.ptr
    cpdef void add(self, int p, ll x): self.ptr.add(p, x)
    cpdef ll sum(self, int l, int r): return self.ptr.sum(l, r)
#
cdef extern from '<atcoder/string>' namespace 'atcoder':
    vector[int] suffix_array(vector[int] s, int upper)
    vector[int] suffix_array(vector[ll] s)
    vector[int] suffix_array(string s)
    vector[int] lcp_array(vector[ll] s, vector[int] sa)
    vector[int] lcp_array(string s, vector[int] sa)
    vector[int] z_algorithm(vector[ll] s)
    vector[int] z_algorithm(string s)
cpdef vector[int] suffix_array_u(vector[int] s, int upper): return suffix_array(s, upper)
cpdef vector[int] suffix_array_l(vector[ll] s): return suffix_array(s)
cpdef vector[int] suffix_array_s(string s): return suffix_array(s)
cpdef vector[int] lcp_array_l(vector[ll] s, vector[int] sa): return lcp_array(s, sa)
cpdef vector[int] lcp_array_s(string s, vector[int] sa): return lcp_array(s, sa)
cpdef vector[int] z_algorithm_l(vector[ll] s): return z_algorithm(s)
cpdef vector[int] z_algorithm_s(string s): return z_algorithm(s)
#
cdef extern from '<atcoder/math>' namespace 'atcoder':
    ll pow_mod(ll x, ll n, ll m)
    ll inv_mod(ll x, ll m)
    pair[ll, ll] crt(vector[ll] r, vector[ll] m)
    ll floor_sum(ll n, ll m, ll a, ll b)
cpdef ll pow_mod_(ll x, ll n, ll m): return pow_mod(x, n, m)
cpdef ll inv_mod_(ll x, ll m): return inv_mod(x, m)
cpdef pair[ll, ll] crt_(vector[ll] r, vector[ll] m): return crt(r, m)
cpdef ll floor_sum_(ll n, ll m, ll a, ll b): return floor_sum(n, m, a, b)
#
cdef extern from '<atcoder/convolution>' namespace 'atcoder':
    vector[ll] convolution[m](vector[ll] a, vector[ll] b)
    vector[ll] convolution_ll(vector[ll] a, vector[ll] b)
cpdef vector[ll] convolution_(vector[ll] a, vector[ll] b): return convolution[MOD](a, b)
cpdef vector[ll] convolution_ll_(vector[ll] a, vector[ll] b): return convolution_ll(a, b)
#
cdef extern from '<atcoder/dsu>' namespace 'atcoder':
    cpdef cppclass dsu:
        dsu(int n)
        int merge(int a, int b)
        bool same(int a, int b)
        int leader(int a)
        int size(int a)
        vector[vector[int]] groups()
cdef class dsu_:
    cdef dsu *ptr
    def __cinit__(self, int n): self.ptr = new dsu(n)
    def __dealloc__(self): del self.ptr
    cpdef int merge(self,a,b): return self.ptr.merge(a,b)
    cpdef bool same(self,a,b): return self.ptr.same(a,b)
    cpdef int leader(self,a): return self.ptr.leader(a)
    cpdef int size(self,a): return self.ptr.size(a)
    cpdef vector[vector[int]] groups(self): return self.ptr.groups()
#
cdef extern from '<atcoder/maxflow>' namespace 'atcoder':
    cdef cppclass mf_graph[Cap]:
        mf_graph(int n)
        int add_edge(int frm, int to, Cap cap)
        Cap flow(int s, int t)
        Cap flow(int s, int t, Cap flow_limit)
        vector[bool] min_cut(int s)
        cppclass edge:
            int frm 'from', to
            Cap cap, flow
            edge(edge &e)
        edge get_edge(int i)
        vector[edge] edges()
        void change_edge(int i, Cap new_cap, Cap new_flow)
cdef class mf_graph_:
    cdef mf_graph[ll] *ptr
    def __cinit__(self, int n): self.ptr = new mf_graph[ll](n)  
    def __dealloc__(self): del self.ptr
    cpdef int add_edge(self, int frm, int to, ll cap): return self.ptr.add_edge(frm, to, cap)
    cpdef ll flow(self, int s, int t): return self.ptr.flow(s, t)
    cpdef ll flow_limit(self, int s, int t, ll flow_limit): return self.ptr.flow(s, t, flow_limit)
    cpdef vector[bool] min_cut(self, int s): return self.ptr.min_cut(s)
    cpdef vector[ll] get_edge(self, int i):
        cdef mf_graph[ll].edge *e = new mf_graph[ll].edge(self.ptr.get_edge(i))
        cdef vector[ll] *ret_e = new vector[ll]()		
        ret_e.push_back(e.frm)
        ret_e.push_back(e.to)
        ret_e.push_back(e.cap)
        ret_e.push_back(e.flow)
        return ret_e[0]
    cpdef vector[vector[ll]] edges(self):
        cdef vector[mf_graph[ll].edge] es = self.ptr.edges()
        cdef vector[vector[ll]] *ret_es = new vector[vector[ll]](es.size())
        for i in range(es.size()):
            ret_es.at(i).push_back(es.at(i).frm)
            ret_es.at(i).push_back(es.at(i).to)
            ret_es.at(i).push_back(es.at(i).cap)
            ret_es.at(i).push_back(es.at(i).flow)
        return ret_es[0]
    cpdef void change_edge(self, int i, ll new_cap, ll new_flow): self.ptr.change_edge(i, new_cap, new_flow)
#
cdef extern from '<atcoder/mincostflow>' namespace 'atcoder':
    cdef cppclass mcf_graph[Cap, Cost]:
        mcf_graph(int n)
        int add_edge(int frm, 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', to
            Cap cap, flow
            Cost cost
            edge(edge &e)
        edge get_edge(int i)
        vector[edge] edges()
cdef class mcf_graph_:
    cdef mcf_graph[ll, ll] *ptr
    def __cinit__(self, int n): self.ptr = new mcf_graph[ll, ll](n)  
    def __dealloc__(self): del self.ptr
    cpdef int add_edge(self, int frm, int to, ll cap, ll cost): return self.ptr.add_edge(frm, to, cap, cost)
    cpdef pair[ll, ll] flow(self, int s, int t): return self.ptr.flow(s, t)
    cpdef pair[ll, ll] flow_limit(self, int s, int t, ll flow_limit): return self.ptr.flow(s, t, flow_limit)
    cpdef vector[pair[ll, ll]] slope(self, int s, int t): return self.ptr.slope(s, t)
    cpdef vector[pair[ll, ll]] slope_limit(self, int s, int t, ll flow_limit): return self.ptr.slope(s, t, flow_limit)
    cpdef vector[ll] get_edge(self, int i):
        cdef mcf_graph[ll, ll].edge *e = new mcf_graph[ll, ll].edge(self.ptr.get_edge(i))
        cdef vector[ll] *ret_e = new vector[ll]()
        ret_e.push_back(e.frm)
        ret_e.push_back(e.to)
        ret_e.push_back(e.cap)
        ret_e.push_back(e.flow)
        ret_e.push_back(e.cost)
        return ret_e[0]
    cpdef vector[vector[ll]] edges(self):
        cdef vector[mcf_graph[ll, ll].edge] es = self.ptr.edges()
        cdef vector[vector[ll]] *ret_es = new vector[vector[ll]](es.size())
        for i in range(es.size()):
            ret_es.at(i).push_back(es.at(i).frm)
            ret_es.at(i).push_back(es.at(i).to)
            ret_es.at(i).push_back(es.at(i).cap)
            ret_es.at(i).push_back(es.at(i).flow)
            ret_es.at(i).push_back(es.at(i).cost)
        return ret_es[0]
#
cdef extern from '<atcoder/scc>' namespace 'atcoder':
    cdef cppclass scc_graph:
        scc_graph(int n)
        void add_edge(int fr, int to)
        vector[vector[int]] scc()
cdef class scc_graph_:
    cdef scc_graph *ptr
    def __cinit__(self, int n): self.ptr = new scc_graph(n)  
    def __dealloc__(self): del self.ptr
    cpdef void add_edge(self, int fr, int to): self.ptr.add_edge(fr, to)
    cpdef vector[vector[int]] scc(self): return self.ptr.scc()
#
cdef extern from '<atcoder/twosat>' namespace 'atcoder':
    cdef cppclass two_sat:
        two_sat(int n)
        void add_clause(int i, bool f, int j, bool g)
        bool satisfiable()
        vector[bool] answer()
cdef class two_sat_:
    cdef two_sat *ptr
    def __cinit__(self, int n): self.ptr = new two_sat(n)
    def __dealloc__(self): del self.ptr
    cpdef void add_clause(self, int i, bool f, int j, bool g): self.ptr.add_clause(i, f, j, g)
    cpdef bool satisfiable(self): return self.ptr.satisfiable()
    cpdef vector[bool] answer(self): return self.ptr.answer()
'''
import os
try:
    from atcoder import *
except:
    open('atcoder.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')

N,M=map(int,input().split())
S=[input() for i in range(N)]
g=mcf_graph_(N*M+2)
s,t=N*M,N*M+1
X=10**9
for i in range(N):
    for j in range(M):
        if S[i][j]=='o':
            g.add_edge(s,i*M+j,1,0)
        if j<M-1 and S[i][j]!='#'!=S[i][j+1]:
            g.add_edge(i*M+j,i*M+j+1,X,0)
        if i<N-1 and S[i][j]!='#'!=S[i+1][j]:
            g.add_edge(i*M+j,(i+1)*M+j,X,0)
        g.add_edge(i*M+j,t,1,X-i-j)
g.flow(s,t)
print(sum([e[3] for e in g.edges() if e[0]!=s and e[1]!=t]))