maehrm

class RollingHash:
    def __init__(self, str, base, mod):
        self.base = base
        self.mod = mod
        self.pow = [1] * (len(str) + 1)
        self.hash = [0] * (len(str) + 1)
        for i in range(len(str)):
            self.hash[i + 1] = (self.hash[i] * base + ord(str[i])) % mod
            self.pow[i + 1] = self.pow[i] * base % mod

maehrm

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __add__(self, other):
        return Point(self.x + other.x, self.y + other.y)

    def __sub__(self, other):
        return Point(self.x - other.x, self.y - other.y)

maehrm

from collections import deque


class Dinic:
    def __init__(self, max_v):
        self.n = max_v
        self.G = [[] for _ in range(self.n)]

    def add_edge(self, fr, to, cap):  # frからtoへ向かう容量capの辺を追加する
        self.G[fr].append([to, cap, len(self.G[to])])

maehrm

from atcoder.maxflow import MFGraph


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


N, M = map(int, input().split())
S = [list(input()) for _ in range(N)]
g = MFGraph(N * M + 2)

maehrm

from collections import deque


class Dinic:
    def __init__(self, max_v):
        self.n = max_v
        self.G = [[] for _ in range(self.n)]

    def add_edge(self, fr, to, cap):  # frからtoへ向かう容量capの辺を追加する
        self.G[fr].append([to, cap, len(self.G[to])])

maehrm

from collections import deque


class Dinic:
    def __init__(self, max_v):
        self.n = max_v
        self.G = [[] for _ in range(self.n)]

    def add_edge(self, fr, to, cap):  # frからtoへ向かう容量capの辺を追加する
        self.G[fr].append([to, cap, len(self.G[to])])

maehrm

from collections import deque


class Dinic:
    def __init__(self, max_v):
        self.n = max_v
        self.G = [[] for _ in range(self.n)]

    def add_edge(self, fr, to, cap):  # frからtoへ向かう容量capの辺を追加する
        self.G[fr].append([to, cap, len(self.G[to])])

maehrm

from collections import deque


class Dinic:
    def __init__(self, max_v):
        self.n = max_v
        self.G = [[] for _ in range(self.n)]

    def add_edge(self, fr, to, cap):  # frからtoへ向かう容量capの辺を追加する
        self.G[fr].append([to, cap, len(self.G[to])])

maehrm

from collections import deque


class Dinic:                    
    def __init__(self, max_v):
        self.n = max_v
        self.G = [[] for _ in range(self.n)]

    def add_edge(self, fr, to, cap):  # frからtoへ向かう容量capの辺を追加する
        self.G[fr].append([to, cap, len(self.G[to])])

maehrm

from atcoder.maxflow import MFGraph

N = 7  # Node数(駅の数)
M = 12  # Edge数(路線の数)

g = MFGraph(N)

g.add_edge(0, 1, 12)  # (0)渋谷 -> (1)新宿   12
g.add_edge(0, 2, 25)  # (0)渋谷 -> (2)表参道 25
g.add_edge(2, 1, 3)  # (2)表参道 -> (1)新宿 3