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 <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#include <cmath>
#include <iomanip>
#include <map>
#include <cstring>
#include <functional>
#include <cctype>
#include <locale>
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(),(a).end()
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
typedef pair<int,int> P;
typedef pair<long long,long long> Pll;
#define fout(num) cout << fixed << setprecision(20) << (num) << endl
//s[i]=tolower(s[i]); islower(s[i]); cout << tolower(s[i])はバグ
//vector<vector<ll>> dp(n,vector<ll>(n))
//2-dim:vector<vector<Type>> vv(n, vector<Type>(m, d));
//3-dim:vector<vector<vector<Type>>> vvv(n, vector<vector<Type>>(m, vector<Type>(l, d)));

//O(FElogV)
template<typename TF,typename TC>
struct Flow{
    static const TC INF_cost;
    struct edge{
        int to;
        TF cap;
        TC cost;
        int rev;
        edge(){}
        edge(int to,TF cap,TC cost,int rev):to(to),cap(cap),cost(cost),rev(rev){}
    };
    vector<vector<edge>> G;
    vector<TC> potential,dist;
    vector<int> prevv,preve;
    Flow(){}
    Flow(int n):G(n),potential(n),dist(n),prevv(n),preve(n){}
    
    void add_edge(int from,int to,TF cap,TC cost){
        G[from].push_back((edge){to,cap,cost,(int)G[to].size()});
        G[to].push_back((edge){from,0,-cost,(int)G[from].size()-1});
    }
    void dijkstra(int s){
        struct P{
            TC first;
            int second;
            P(TC first,int second):first(first),second(second){}
            bool operator<(const P &a)const{return a.first<first;}
            //直感と逆なので注意
        };
        priority_queue<P> que;
        fill(dist.begin(),dist.end(),INF_cost);
        dist[s]=0;
        que.push((P){dist[s],s});
        while(!que.empty()){
            P fr=que.top(); que.pop();
            int v=fr.second;
            if(dist[v]<fr.first) continue;
            for(int i=0;i<(int)G[v].size();i++){
                edge &e=G[v][i];
                if(e.cap==0) continue;
                if(dist[v]+e.cost+potential[v]-potential[e.to]<dist[e.to]){
                    dist[e.to]=dist[v]+e.cost+potential[v]-potential[e.to];
                    prevv[e.to]=v;
                    preve[e.to]=i;
                    que.push((P){dist[e.to],e.to});
                }
            }
        }
    }
    TC min_cost_flow(int s,int t,TF f,bool &ok){
        TC res=0;
        fill(potential.begin(),potential.end(),0);
        while(f>0){
            dijkstra(s);
            if(dist[t]==INF_cost){
                ok=false;
                return res;
            }
            for(int v=0;v<(int)potential.size();v++){
                if(dist[v]<INF_cost) potential[v]=potential[v]+dist[v];
            }
            TF d=f;
            for(int v=t;v!=s;v=prevv[v]){
                d=min(d,G[prevv[v]][preve[v]].cap);
            }
            f-=d;
            res+=potential[t]*d;
            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;
            }
        }
        ok=true;
        return res;
    }
    pair<TF,TC> get_edge(int from,int to){
        return {G[from][to].cap,G[from][to].cost};
    }
};
template<typename TF, typename TC> const TC Flow<TF,TC>::INF_cost = numeric_limits<TC>::max()/2;

signed main(){
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    const ll MAX = 1e9+1;
    ll N,K; cin >> N >> K;
    //s=0, 1,2,..,n n+1,n+2,...,n+n, n+n+1
    Flow<ll,ll> fl(int(2*N+2));
    for(int i=1;i<=N;i++) fl.add_edge(0,i,K,0);
    for(int i=(int)N+1;i<=N+N;i++) fl.add_edge(i,int(N+N+1),K,0);
    
    fl.add_edge(0,int(N+N+1),N*K,MAX); //流量N*K以下
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            ll a; cin >> a;
            a=MAX-a;
            fl.add_edge(i,int(j+N),1,a);
        }
    }
    bool ok=true;
    ll res=fl.min_cost_flow(0,int(N+N+1),N*K,ok);
    cout << N*K*MAX-res << endl;
    for(int i=1;i<=N;i++){
        for(auto e:fl.G[i]){
            //cout << e.cost << " " <<e.rev<<" ";
            if(e.cost==0) continue;
            else if(e.cap==0) cout << 'X';
            else cout << '.';
        }
        cout << "\n";
    }
}