macro_rules! read_line_to_tuple {
    ( $( $t:ty ),* ) => {{
        let mut input = String::new();
        std::io::stdin().read_line(&mut input).unwrap();
        let mut iter = input.split_whitespace();
        ( $( iter.next().unwrap().parse::<$t>().unwrap() ),* )
    }};
}

macro_rules! read_line_to_collection {
    ( $t:ty ) => {{
        let mut input = String::new();
        std::io::stdin().read_line(&mut input).unwrap();
        let iter = input.split_whitespace();
        iter.map(|x| x.parse().unwrap()).collect::<$t>()
    }};
}

use std::collections::BinaryHeap;
use std::cmp::Reverse;

#[derive(Clone, Copy)]
struct Edge {
    to: usize, rev: usize, cap: i64, cost: i64,
}

impl Edge {
    fn new(to: usize, rev: usize, cap: i64, cost: i64) -> Edge {
        Edge { to, rev, cap, cost, }
    }
}

struct PrimalDual {
    n: usize,
    g: Vec<Vec<Edge>>,
}

impl PrimalDual {
    fn new(n: usize) -> PrimalDual {
        PrimalDual {
            n,
            g: vec![vec![]; n],
        }
    }

    fn add_edge(&mut self, from: usize, to: usize, cap: i64, cost: i64) {
        let rev = self.g[to].len();
        self.g[from].push(Edge::new(to, rev, cap, cost));
        let rev = self.g[from].len() - 1;
        self.g[to].push(Edge::new(from, rev, 0, -cost));
    }

    fn min_cost_flow(&mut self, s: usize, t: usize, flow_limit: i64) -> i64 {
        let mut res = 0;
        let mut heap = BinaryHeap::new();
        let mut min_cost = vec![0; self.n];
        let mut prev_v = vec![!0; self.n];
        let mut prev_e = vec![!0; self.n];

        let mut flow = 0;
        while flow < flow_limit {
            min_cost.iter_mut().for_each(|c| *c = std::i64::MAX);
            prev_v.iter_mut().for_each(|v| *v = !0);
            prev_e.iter_mut().for_each(|e| *e = !0);
            heap.push((Reverse(0), s));
            min_cost[s] = 0;
            while let Some((Reverse(cost), v)) = heap.pop() {
                for (i, e) in self.g[v].iter().enumerate() {
                    let next_cost = cost + e.cost;
                    if e.cap > 0 && next_cost < min_cost[e.to] {
                        min_cost[e.to] = next_cost;
                        prev_v[e.to] = v;
                        prev_e[e.to] = i;
                        heap.push((Reverse(next_cost), e.to));
                    }
                }
            }

            let mut v = t;
            while v != s {
                self.g[prev_v[v]][prev_e[v]].cap -= 1;
                let rev = self.g[prev_v[v]][prev_e[v]].rev;
                self.g[v][rev].cap += 1;
                res += self.g[prev_v[v]][prev_e[v]].cost;
                v = prev_v[v];
            }

            flow += 1;
        }

        res
    }
}

const GETA: i64 = 1 << 30;

fn main() {
    let (n, k) = read_line_to_tuple!(usize, i64);
    let a: Vec<Vec<i64>> = {
        (0..n)
            .map(|_| read_line_to_collection!(Vec<i64>))
            .collect()
    };

    let mut pd = PrimalDual::new(2 * n + 2);
    let (s, t) = (2 * n, 2 * n + 1);

    pd.add_edge(s, t, n as i64 * k, GETA);

    for i in 0..n {
        pd.add_edge(s, i, k, 0);
        pd.add_edge(n + i, t, k, 0);
    }

    for i in 0..n {
        for j in 0..n {
            pd.add_edge(i, n + j, 1, GETA - a[i][j]);
        }
    }

    let mut ans = Vec::with_capacity(n + 1);
    ans.push(
        (n as i64 * k * GETA - pd.min_cost_flow(s, t, n as i64 * k))
            .to_string()
    );

    let mut grid: Vec<Vec<char>> = {
        (0..n).map(|_| vec!['.'; n]).collect()
    };
    for v in 0..n {
        for e in &pd.g[v] {
            if e.to != s && e.to != t && v < e.to && e.cap == 0 {
                grid[v][e.to - n] = 'X';
            }
        }
        ans.push(grid[v].iter().collect());
    }
    println!("{}", ans.join("\n"));
}

Measured memory_bytes: 2484