p02562 AtCoder Library Practice Contest - MinCostFlow
You are given a grid of N rows and M columns. The square at the i-th row and j-th column will be denoted as (i,j). A nonnegative integer A_{i,j} is written for each square (i,j).

You choose some of the squares so that each row and column contains at most K chosen squares. Under this constraint, calculate the maximum value of the sum of the integers written on the chosen squares. Additionally, calculate a way to choose squares that acheives the maximum.

Constraints

* 1 \leq N \leq 50
* 1 \leq K \leq N
* 0 \leq A_{i,j} \leq 10^9
* All values in Input are integer.

Input

Input is given from Standard Input in the following format:


N K
A_{1,1} A_{1,2} \cdots A_{1,N}
A_{2,1} A_{2,2} \cdots A_{2,N}
\vdots
A_{N,1} A_{N,2} \cdots A_{N,N}


Output

On the first line, print the maximum value of the sum of the integers written on the chosen squares.

On the next N lines, print a way that achieves the maximum.

Precisely, output the strings t_1,t_2,\cdots,t_N, that satisfies t_{i,j}=`X` if you choose (i,j) and t_{i,j}=`.` otherwise.

You may print any way to choose squares that maximizes the sum.

Examples

Input

3 1
5 3 2
1 4 8
7 6 9


Output

19
X..
..X
.X.


Input

3 2
10 10 1
10 10 1
1 1 10


Output

50
XX.
XX.
..X
```python
import heapq
class mcf_graph:
    def __init__(self, n=0):
        self._n = n
        self.g = [[] for _ in range(n)]
        self.pos = []
    
    def add_edge(self, frm, to, cap, cost):
        m = len(self.pos)
        e1 = self._edge(to, cap, cost)
        e2 = self._edge(frm, 0, -cost)
        e1.rev = e2
        e2.rev = e1
        self.pos.append(e1)
        self.g[frm].append(e1)
        self.g[to].append(e2)
        return m
    
    class edge:
        def __init__(self, frm, to, cap, flow, cost):
            self.frm = frm
            self.to = to
            self.cap = cap
            self.flow = flow
            self.cost = cost
        
        def __iter__(self):
            yield self.frm
            yield self.to
            yield self.cap
            yield self.flow
            yield self.cost
    
    def get_edge(self, i):
        e = self.pos[i]
        re = e.rev
        return self.edge(re.to, e.to, e.cap + re.cap, re.cap, e.cost)
    
    def edges(self):
        return [self.get_edge(i) for i in range(len(self.pos))]
    
    def flow(self, s, t, flow_limit=float('inf')):
        return self.slope(s, t, flow_limit)[-1]
    
    def slope(self, s, t, flow_limit=float('inf')):
        pop, push = heapq.heappop, heapq.heappush
        n = self._n
        g = self.g
        dual = [0] * n
        dist = [0] * n
        pv = [0] * n
        pe = [None] * n
        vis = [False] * n
        INF = float('inf')    
        flow = 0
        cost = 0
        prev_cost = -1
        result = [(flow, cost)]
        while flow < flow_limit:
            for i in range(n):
                dist[i] = INF
                vis[i] = False
            dist[s] = 0
            que = [(0, s)]
            while que:
                _, v = pop(que)
                if vis[v]:
                    continue
                vis[v] = True
                if v == t:
                    break
                for e in g[v]:
                    w = e.to
                    if vis[w] or not e.cap:
                        continue
                    ndist = dist[v] + e.cost - dual[w] + dual[v]
                    if ndist < dist[w]:
                        dist[w] = ndist
                        pv[w] = v
                        pe[w] = e
                        push(que, (dist[w], w))
            else:
                break
            for v in range(n):
                if not vis[v]:
                    continue
                dual[v] -= dist[t] - dist[v]
            c = flow_limit - flow
            v = t
            while v != s:
                c = min(c, pe[v].cap)
                v = pv[v]
            v = t
            while v != s:
                e = pe[v]
                e.cap -= c
                e.rev.cap += c
                v = pv[v]
            d = -dual[s]
            flow += c
            cost += c * d
            if prev_cost == d:
                result[-1] = (flow, cost)
            else:
                result.append((flow, cost))
            prev_cost = cost
        return result
    
    class _edge:
        def __init__(self, to, cap, cost):
            self.to = to
            self.cap = cap
            self.cost = cost
    
    class _edge:
        def __init__(self, to, cap, cost):
            self.to = to
            self.cap = cap
            self.cost = cost

n, k = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
mx = max(aij for ai in a for aij in ai)
s = n * n
t = s + 1
rs = t + 1
cs = rs + n
vcnt = cs + n
d = mcf_graph(vcnt)
for i in range(n):
    d.add_edge(s, rs + i, k, 0)
for i in range(n):
    for j in range(n):
        d.add_edge(rs + i, i * n + j, 1, mx - a[i][j])
for i in range(n):
    for j in range(n):
        d.add_edge(i * n + j, cs + j, 1, 0)
for j in range(n):
    d.add_edge(cs + j, t, k, 0)
d.add_edge(s, t, n * n, mx)
_, res = d.flow(s, t, n * n)
print(n * n * mx - res)
ans = [['.'] * n for _ in range(n)]
for frm, to, cap, flow, cost in d.edges():
    if frm < n * n and flow:
        i, j = frm // n, frm % n
        ans[i][j] = 'X'
for t in ans:
    print(''.join(t))
```