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 <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <complex>

using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops, no-stack-protector")
#pragma GCC target("avx,avx2,fma")

long long ans = 0, nn;
vector<vector<char>> v;



class min_cost_flow {
public:

	struct edge_node {
		long long to;
		long long capacity, flow;
		long long cost;
		long long reverse_id;
	};

	long long VERYBIG = 1LL << 61;
	long long n, f, mf, totalcost;
	long long s, t;		// source and sink
	vector<vector<edge_node>> adj;
	vector<long long> pp, ppid;

	min_cost_flow(long long nn, long long start, long long terminal) {		// initialize network with n nodes, starting from 0
		n = nn;
		s = start;
		t = terminal;

		adj.clear();
		adj.resize(nn);
	}


	void add_path(long long a, long long b, long long forward_capacity, long long backward_capacity = 0, long long forward_cost = 0, long long backward_cost = 0) {	// one directional
		long long ida = adj[a].size(), idb = adj[b].size();
		adj[a].push_back({ b, forward_capacity, 0, forward_cost, idb });
		adj[b].push_back({ a, backward_capacity, 0, backward_cost, ida });
	}

	void clear_flow() {		// reset all flow to zero from network 
		long long i;
		for (i = 0; i < n; i++) {
			for (auto p : adj[i]) p.flow = 0;
		}
	}

	void augment(long long v, long long maxflow) {
		if (v == s) {
			f = maxflow;		// external variable
		}
		else if (pp[v] != -1) {
			long long parent = pp[v], pid = ppid[v], rid = adj[parent][pid].reverse_id;
			long long available_flow = adj[parent][pid].capacity - adj[parent][pid].flow;

			if (maxflow < available_flow) augment(parent, maxflow);
			else augment(parent, available_flow);

			adj[parent][pid].flow += f;
			adj[v][rid].flow -= f;

			totalcost += f * (adj[parent][pid].cost - adj[v][rid].cost);
		}
	}

	void solve_flow() {		// returns total cost and mf
		mf = 0;
		totalcost = 0;

		while (1) {
			long long i, j, k;
			vector<long long> dist;
			dist.assign(n, VERYBIG);
			dist[s] = 0;

			queue<long long> q;
			q.push(s);

			pp.assign(n, -1);		// polong long back to parents
			ppid.assign(n, -1);		// polong long back to the edge id in parents

			while (!q.empty()) {
				long long u = q.front(), v;
				q.pop();
				for (i = 0; i < adj[u].size(); i++) {
					v = adj[u][i].to;
					if ((adj[u][i].flow < adj[u][i].capacity) && (dist[v] > dist[u] + adj[u][i].cost)) {
						dist[v] = dist[u] + adj[u][i].cost;
						q.push(v);
						pp[v] = u;
						ppid[v] = i;
					}
				}
			}

			f = 0;
			augment(t, VERYBIG);
			if (f == 0) break;
			if (f == VERYBIG) break;
			mf += f;

			//totalcost /= 2;

			long long x = ((long long)(1E9) * mf * 2 - totalcost) / 2;

			if (x > ans) {
				ans = x;
				v.assign(nn, vector<char>(nn, '.'));

				for (i = 0; i < nn; i++) {
					for (auto p : adj[i + 1]) {
						if ((p.flow == 1) && (p.to > nn * 2))
							v[i][p.to - nn * 2 - i * nn - 1] = 'X';
					}
				}
			}

		}

	}
};



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

	long long n, kk, i, j, k, id, INF = 1E9;
	cin >> n >> kk;
	vector<vector<long long>> a(n, vector<long long>(n));
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			cin >> a[i][j];
			a[i][j] = INF - a[i][j];
		}
	}

	min_cost_flow fl(n * n + 2 * n + 2, 0, n * n + 2 * n + 1);

	for (i = 0; i < n; i++) {
		fl.add_path(0, i + 1, kk, 0, 0, 0);							// start --> row
		fl.add_path(n + i + 1, n * n + 2 * n + 1, kk, 0, 0, 0);		// column --> terminal
		fl.add_path(i + 1, n + i + 1, kk, 0, INF, -INF);
	}

	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			id = n * 2 + i * n + j + 1;
			fl.add_path(i + 1, id, 1, 0, a[i][j], -a[i][j]);
			fl.add_path(id, n + j + 1, 1, 0, 0, 0);
		}
	}

	nn = n;

	fl.solve_flow();


	cout << ans << "\n";
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) cout << v[i][j];
		cout << "\n";
	}


	return 0;
}