Problem: 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

Solution (in PYTHON3):

Solution:
# Date [ 2020-09-12 01:35:29 ]
# Problem [ e.py ]
# Author Koki_tkg
# もうすぐ翻訳終了

from heapq import heappop, heappush
class mcf_graph:
    numeric_limits_max = 10 ** 18

    def __init__(self, n: int):
        self._n = n
        self.g = [[] for _ in range(n)]
        self.pos = []

    def add_edge(self, _from: int, _to: int, cap: int, cost: int) -> int:
        assert 0 <= _from and _from < self._n
        assert 0 <= _to and _to < self._n
        m = len(self.pos)
        self.pos.append((_from, len(self.g[_from])))
        self.g[_from].append(self._edge(_to, len(self.g[_to]), cap, cost))
        self.g[_to].append(self._edge(_from, len(self.g[_from]) - 1, 0, -cost))
        return m
    
    class edge:
        def __init__(s, _from: int, _to: int, cap: int, flow: int, cost: int):
            s._from = _from; s._to = _to; s.cap = cap; s.flow = flow; s.cost = cost
    
    def get_edge(self, i: int) -> edge:
        m = len(self.pos)
        assert 0 <= i and i < m
        _e = self.g[self.pos[i][0]][self.pos[i][1]]
        _re = self.g[_e.to][_e.rev]
        return self.edge(self.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap, _e.cost)
    
    def edges(self) -> list:
        m = len(self.pos)
        result = [self.get_edge(i) for i in range(m)]
        return result
    
    def flow(self, s: int, t: int) -> edge:
        return self.flow_(s, t, self.numeric_limits_max)
    def flow_(self, s: int, t: int, flow_limit: int) -> edge:
        return self.__slope(s, t, flow_limit)[-1]
    
    def slope(self, s: int, t: int) -> list:
        return self.slope_(s, t, self.numeric_limits_max)
    def slope_(self, s: int, t: int, flow_limit: int) -> list:
        return self.__slope(s, t, flow_limit)
    
    def __slope(self, s: int, t: int, flow_limit: int) -> list:
        assert 0 <= s and s < self._n
        assert 0 <= t and t < self._n
        assert s != t
        dual = [0] * self._n; dist = [0] * self._n
        pv, pe = [-1] * self._n, [-1] * self._n
        vis = [False] * self._n
        
        def dual_ref():
            for i in range(self._n):
                dist[i] = self.numeric_limits_max
                pv[i] = -1
                pe[i] = -1
                vis[i] = False
            class Q:
                def __init__(s, key: int, to: int):
                    s.key = key; s.to = to
                def __lt__(s, r): return s.key < r.key
            que = []
            dist[s] = 0
            heappush(que, Q(0, s))
            while que:
                v = heappop(que).to
                if vis[v]: continue
                vis[v] = True
                if v == t: break
                for i in range(len(self.g[v])):
                    e = self.g[v][i]
                    if vis[e.to] or not e.cap: continue
                    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
                        heappush(que, Q(dist[e.to], e.to))
            if not vis[t]: return False
            for v in range(self._n):
                if not vis[v]: continue
                dual[v] -= dist[t] - dist[v]
            return True

        flow = 0
        cost = 0; prev_cost = -1
        result = []
        result.append((flow, cost))
        while flow < flow_limit:
            if not dual_ref(): break
            c = flow_limit - flow
            v = t
            while v != s:
                c = min(c, self.g[pv[v]][pe[v]].cap)
                v = pv[v]
            v = t
            while v != s:
                e = self.g[pv[v]][pe[v]]
                e.cap -= c
                self.g[v][e.rev].cap += c
                v = pv[v]
            d = -dual[s]
            flow += c
            cost += c * d
            if prev_cost == d:
                result.pop()
            result.append((flow, cost))
            prev_cost = cost
        return result
    class _edge:
        def __init__(s, to: int, rev: int, cap: int, cost: int):
            s.to = to; s.rev = rev; s.cap = cap; s.cost = cost
        

import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

def Main():
    n, k = read_ints()
    a = [read_int_list() for _ in range(n)]
    mcf = mcf_graph(n * 2 + 2)
    s = n * 2
    t = n * 2 + 1

    for i in range(n):
        mcf.add_edge(s, i, k, 0)
        mcf.add_edge(i + n, t, k, 0)
    mcf.add_edge(s, t, n * k, INF)
    
    for i in range(n):
        for j in range(n):
            mcf.add_edge(i, n + j, 1, INF - a[i][j])
    
    result = mcf.flow_(s, t, n * k)
    print(n * k * INF - result[1])
    grid = [['.'] * n for _ in range(n)]
    edges = mcf.edges()
    for e in edges:
        if e._from == s or e._to == t or e.flow == 0: continue
        grid[e._from][e._to - n] = 'X'
    print(*[''.join(g) for g in grid], sep='\n')

if __name__ == '__main__':
    Main()