#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int n;
int m[20][20];
int ans = 0;
vector<int> best;

void work(vector<int>& p) {
    int curr = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (p[i] != p[j]) curr += m[i][j];
        }
    }
    if (curr > ans) {
        ans = curr;
        best = p;
    }
}

void go(vector<int>& p) {
    if (p.size() == n) {
        work(p);
    } else {
        for (int i = 0; i < 2; ++i) {
            p.push_back(i);
            go(p);
            p.pop_back();
        }
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> m[i][j];
        }
    }
    vector<int> p;
    go(p);
    cout << ans << "\n";
    for (int i = 0; i < n; ++i) {
        cout << best[i] + 1 << " ";
    }
    cout << "\n";
    return 0;
}