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<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<complex>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
#include <numeric>
using namespace std;
using Complex = complex<double>;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll inf = 1145141919810364364LL;
const double EPS = 1e-10;
double PI = acos(-1.0);
#define all(x) (x).begin(),(x).end()
#define puts(x) cout << x << endl
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)
 
int N, K;
int rec[110][110];
 
//primal-dual
struct edge { ll to, cap, cost, rev; };
 
const int MAX_V = 110;
int V;
vector<edge>G[MAX_V];
ll dist[MAX_V],h[MAX_V];
ll ans = inf;
int prevv[MAX_V], preve[MAX_V];
 
void add_edge(int from, int to, int cap, int cost) {
	edge fe = { to,cap,cost,(int)G[to].size() };
	edge toe = { from,0,-cost,(int)G[from].size() };
	G[from].pb(fe);
	G[to].pb(toe);
}
 
ll min_cost_flow(int s, int t, int f) {
	ll res = 0;
	int flag = 0;
	while (f > 0) {
		for (int i = 0; i < V; i++)dist[i] = inf;
		dist[s] = 0;

		if (flag == 0) {
			for (int i = 0; i < V - 1; i++) {
				for (int j = 0; j < V; j++) {
					for (int k = 0; k < G[j].size(); k++) {
						edge &e = G[j][k];
						if (dist[j] == inf)continue;
						if (e.cap > 0 && dist[e.to] > dist[j] + e.cost) {
							dist[e.to] = dist[j] + e.cost;
							prevv[e.to] = j;
							preve[e.to] = k;
						}
					}
				}
			}
			flag = 1;
		}
		else {
			min_priority_queue<pair<ll, ll>>que;
			que.push({ 0,s });
			while (que.size()) {
				auto p = que.top();
				que.pop();
				int v = p.second;
				if (dist[v] < p.first)continue;
				for (int i = 0; i < G[v].size(); i++) {
					edge &e = G[v][i];
					if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
						dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
						prevv[e.to] = v;
						preve[e.to] = i;
						que.push({dist[e.to],e.to});
					}
				}
			}
		}

		if (dist[t] == inf)return -1;
		for (int i = 0; i < V; i++)h[i] += dist[i];


		//s-t最短路に沿って目いっぱい流す
		ll d = f;
		for (int v = t; v != s; v = prevv[v]) {
			d = min(d, G[prevv[v]][preve[v]].cap);
		}
		f -= d;
		res += d * h[t];
		for (int v = t; v != s; v = prevv[v]) {
			edge &e = G[prevv[v]][preve[v]];
			e.cap -= d;
			G[v][e.rev].cap += d;
		}
      
      if (ans > res) {
			ans = res;
			memset(rec,0,sizeof(rec));
			for (int i = 1; i <= N; i++) {
				for (int j = 0; j < G[i].size(); j++) {
					edge e = G[i][j];
					if (e.cap == 0)rec[i][e.to] = 1;
				}
			}
		}
	}
	return res;
}
 
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
 
	cin >> N >> K;
	V = 2 * N + 2;
	for (int i = 1; i <= N; i++)add_edge(0,i,K,0);
	for (int i = N + 1; i <= 2 * N; i++)add_edge(i,2*N+1,K,0);
	for (int i = 1; i <= N; i++) {
		for (int j = N+1; j <= 2*N; j++) {
			int A;
			cin >> A;
			add_edge(i,j,1,-A);
		}
	}
	min_cost_flow(0, 2 * N + 1, 60 * 60);
 
 
	puts(-ans);
	for (int i = 1; i <= N; i++) {
		for (int j = N+1; j <= 2*N; j++) {
			if(rec[i][j])cout << "X";
			else cout << ".";
		}
		puts("");
	}
 
 
	return 0;
}