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:
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
#include <memory>
#include <regex>
using namespace std;

template <class T>
class EdgeBase{
public:
    int to, rev, cap, flow;
    T cost;
    EdgeBase(int to = -1, int cap = 0, T cost = 0, int rev = -1, int flow = 0)
    {
        this->to = to;
        this->cap = cap;
        this->cost = cost;
        this->rev = rev;
        this->flow = flow;
    }
};
typedef EdgeBase<long long> Edge;

template<class T>
T minCostFlow(vector<vector<EdgeBase<T> > >& edges_org, int source, int sink, int flow)
{
    static const T INF = numeric_limits<T>::max();
    static const T EPS = static_cast<T>(1.0e-10);

    int n = edges_org.size();
    vector<vector<EdgeBase<T> > > edges(n);
    for(int i=0; i<n; ++i){
        for(unsigned j=0; j<edges_org[i].size(); ++j){
            const EdgeBase<T>& e = edges_org[i][j];
            edges[i].push_back(EdgeBase<T>(e.to, e.cap, e.cost, edges[e.to].size()));
            edges[e.to].push_back(EdgeBase<T>(i, 0, -e.cost, edges[i].size()-1));
        }
    }

    vector<T> h(n, 0);
    vector<int> prevV(n);
    vector<int> prevE(n);

    T ans = 0;
    while(flow > 0){
        vector<T> dist(n, INF);
        dist[source] = 0;
        priority_queue<pair<T,int> ,vector<pair<T,int> >, greater<pair<T,int> > > q;
        q.push(make_pair(0, source));

        while(!q.empty()){
            pair<T, int> p = q.top();
            q.pop();
            int v = p.second;
            if(dist[v] < p.first - EPS)
                continue;
            for(unsigned i=0; i<edges[v].size(); ++i){
                EdgeBase<T> e = edges[v][i];
                if(e.cap - e.flow > 0 && dist[v] + e.cost + h[v] - h[e.to] < dist[e.to] - EPS){
                    dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
                    prevV[e.to] = v;
                    prevE[e.to] = i;
                    q.push(make_pair(dist[e.to], e.to));
                }
            }
        }
        if(dist[sink] >= INF)
            return -1;
        for(int i=0; i<n; ++i)
            h[i] += dist[i];

        int g = flow;
        for(int i=sink; i!=source; i=prevV[i])
            g = min(g, edges[prevV[i]][prevE[i]].cap - edges[prevV[i]][prevE[i]].flow);
        for(int i=sink; i!=source; i=prevV[i]){
            EdgeBase<T>& e = edges[prevV[i]][prevE[i]];
            e.flow += g;
            edges[i][e.rev].flow -= g;
        }
        flow -= g;
        ans += g * h[sink];
    }

    for(int i=0; i<n; ++i){
        for(unsigned j=0; j<edges_org[i].size(); ++j){
            edges_org[i][j].flow = edges[i][j].flow;
        }
    }

    return ans;
}

const int MAX = 1000000000;

int main()
{
    int n, k;
    cin >> n >> k;
    vector<vector<int> > a(n, vector<int>(n));
    for(int i=0; i<n; ++i){
        for(int j=0; j<n; ++j){
            cin >> a[i][j];
        }
    }

    vector<vector<Edge> > edges(n*(n+2)+2);
    int source = edges.size() - 2;
    int sink = edges.size() - 1;
    edges[source].push_back(Edge(sink, k * n, MAX));
    for(int i=0; i<n; ++i){
        edges[source].push_back(Edge(i, k, 0));
        edges[n+i].push_back(Edge(sink, k, 0));
        for(int j=0; j<n; ++j){
            edges[i].push_back(Edge(2*n+i*n+j, 1, MAX - a[i][j]));
            edges[2*n+i*n+j].push_back(Edge(n+j, 1, 0));
        }
    }

    long long ans = (long long)MAX * k * n;
    ans -= minCostFlow(edges, source, sink, k * n);
    cout << ans << endl;

    for(int i=0; i<n; ++i){
        for(int j=0; j<n; ++j){
            if(edges[i][j].flow == 0)
                cout << ".";
            else
                cout << 'X';
        }
        cout << endl;
    }

    return 0;
}