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 CPP):

Solution:
#include <bits/stdc++.h>

using namespace std;
using int64 = long long;

constexpr int DEBUG = 0;

struct CostFlowEdge {
  const int from, to;
  const int64 cap;
  const int64 cost;
  CostFlowEdge(int from, int to, int64 cap, int64 cost)
      : from(from), to(to), cap(cap), cost(cost) {}
};

// Returns a pair of (flow, cost).
tuple<int64, int64, vector<int64>> MinCostFlow(
    int n, const vector<CostFlowEdge>& edges, int s, int t, int64 flow_cap) {
  constexpr int64 INF = INT64_MAX / 4;  // Update this when it doesn't work.

  int m = edges.size();
  
  vector<vector<tuple<CostFlowEdge, int>>> graph(n);
  vector<int64> res_caps(2 * m);  // Edge ID to residual cap
  vector<int64> costs(2 * m);  // Edge ID to original cost
  vector<int64> res_costs(2 * m);  // Edge ID to residual cost
  vector<int> to_reverse(2 * m, -1);  // Edge ID to the reverse edge ID

  for (int i = 0; i < m; i++) {
    const auto& edge = edges[i];
    graph[edge.from].push_back(make_tuple(edge, i));
    graph[edge.to].push_back(
        make_tuple(CostFlowEdge(edge.to, edge.from, 0, -edge.cost), m + i));
    res_caps[i] = edge.cap;
    costs[i] = edge.cost;
    costs[m + i] = -edge.cost;
    res_costs[i] = edge.cost;
    res_costs[m + i] = -edge.cost;
    to_reverse[i] = m + i;
    to_reverse[m + i] = i;
  }

  int64 total_flow = 0;
  int64 total_cost = 0;
  struct State {
    int v, parent, last_edge;
    int64 weight;
  };
  auto compare_state = [](State s1, State s2) {
    return s1.weight > s2.weight;
  };
  while (total_flow < flow_cap) {
    priority_queue<State, vector<State>, decltype(compare_state)>
        pq(compare_state);
    pq.push(State({s, -1, -1, 0}));
    vector<int64> distances(n, INF);
    vector<int> parents(n, -1);
    vector<int> last_edges(n, -1);
    vector<int> visited(n);
    while(!pq.empty()) {
      State s = pq.top();
      pq.pop();
      if (visited[s.v]) continue;
      visited[s.v] = true;
      distances[s.v] = s.weight;
      parents[s.v] = s.parent;
      last_edges[s.v] = s.last_edge;
      for (const auto& edge_tuple : graph[s.v]) {
        const auto& edge = get<0>(edge_tuple);
        int edge_id = get<1>(edge_tuple);
        if (res_caps[edge_id] == 0 || visited[edge.to]) continue;
        State next =
            State({edge.to, s.v, edge_id, s.weight + res_costs[edge_id]});
        pq.push(next);
      }
    }

    if (distances[t] == INF) return {total_flow, total_cost, res_caps};

    int cur = t;
    vector<int> path;
    while (cur != s) {
      path.push_back(last_edges[cur]);
      cur = parents[cur];
    }

    int64 inc = flow_cap - total_flow;
    for (int edge_id : path) {
      inc = min(inc, res_caps[edge_id]);
    }

    total_flow += inc;

    for (int edge_id : path) {
      total_cost += costs[edge_id] * inc;
      res_caps[edge_id] -= inc;
      res_caps[to_reverse[edge_id]] += inc;
    }

    for (int i = 0; i < m; i++) {
      res_costs[i] += distances[edges[i].from] - distances[edges[i].to];
      res_costs[m + i] -= distances[edges[i].from] - distances[edges[i].to];
    }
  }
  
  return {total_flow, total_cost, res_caps};
}

template<typename T>
vector<vector<T>> Make2DVector(int d1, int d2, T default_value) {
  return vector<vector<T>>(d1, vector<T>(d2, default_value));
}

constexpr int64 MAX_COST = 1E9;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n, k;
  cin >> n >> k;
  vector<vector<int64>> x_matrix = Make2DVector(n, n, 0LL);
  for (int r = 0; r < n; r++) {
    for (int c = 0; c < n; c++) {
      cin >> x_matrix[r][c];
    }
  }

  vector<int> row_vertex_ids(n);
  vector<int> col_vertex_ids(n);
  for (int i = 0; i < n; i++) {
    row_vertex_ids[i] = n * n + i;
    col_vertex_ids[i] = n * n + n + i;
  }
  int s = n * n + 2 * n;
  int t = n * n + 2 * n + 1;

  vector<CostFlowEdge> edges;
  for (int r = 0; r < n; r++) {
    edges.emplace_back(s, row_vertex_ids[r], k, 0);
  }
  for (int r = 0; r < n; r++) {
    for (int c = 0; c < n; c++) {
      edges.emplace_back(row_vertex_ids[r], r * n + c, 1, MAX_COST - x_matrix[r][c]);
      edges.emplace_back(r * n + c, col_vertex_ids[c], 1, 0);
    }
  }
  for (int c = 0; c < n; c++) {
    edges.emplace_back(col_vertex_ids[c], t, k, 0);
  }

  for (int r = 0; r < n; r++) {
    edges.emplace_back(row_vertex_ids[r], t, k, MAX_COST);
  }

  const auto [flow, cost, res_caps] = MinCostFlow(n * n + 2 * n + 2, edges, s, t, n * n);
  int64 value = MAX_COST * flow - cost;
  cout << value << endl;

  vector<string> output(n, string(n, '.'));
  for (int i = 0; i < edges.size(); i++) {
    if (edges[i].to < n * n) {
      if (res_caps[i] == 0) {
        int r = edges[i].to / n;
        int c = edges[i].to % n;
        output[r][c] = 'X';
      }
    }
  }

  for (int r = 0; r < n; r++) {
    cout << output[r] << endl;
  }
}