#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
int n;
int arr[20][20] = { 0, };
int cnt = 0;
int check[20] = { 0 };
int minn = 100000000;
void solve(int start) {
if (cnt == n / 2) { // 출력한다.
int size1 = 0;
int size2 = 0;
int num1 = 0;
int num2 = 0;
int t1[10] = { 0 };
int t2[10] = { 0 };
for (int i = 0; i < n; i++) {
if (check[i] == 1) {
t1[size1] = i;
size1++;
}
else {
t2[size2] = i;
size2++;
}
}
cout << size1 << " " << size2 << endl;
for (int i = 0; i < n; i++) {
cout << check[i] << " ";
}
cout << endl;
for (int i = 0; i <= size1; i++) {
for (int j = 0; j <= size1; j++) {
num1 += arr[t1[i]][t1[j]];
num2 += arr[t2[i]][t2[j]];
}
}
if (minn > abs(num1 - num2))
minn = abs(num1 - num2);
cout << cnt << endl;
return;
}
else {
for (int i = start; i < n; i++) {
cnt++;
check[i] = 1;
solve(start + 1);
check[i] = 0;
cnt--;
}
}
if (cnt == 0)
return;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int num;
cin >> num;
arr[i][j] = num;
}
}
solve(0);
cout << minn;
return 0;
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPGFsZ29yaXRobT4KI2luY2x1ZGU8dmVjdG9yPgojaW5jbHVkZTxzdGFjaz4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKaW50IG47CmludCBhcnJbMjBdWzIwXSA9IHsgMCwgfTsKaW50IGNudCA9IDA7CmludCBjaGVja1syMF0gPSB7IDAgfTsKaW50IG1pbm4gPSAxMDAwMDAwMDA7Cgp2b2lkIHNvbHZlKGludCBzdGFydCkgewoJaWYgKGNudCA9PSBuIC8gMikgeyAvLyDstpzroKXtlZzri6QuCgkJaW50IHNpemUxID0gMDsKCQlpbnQgc2l6ZTIgPSAwOwoJCWludCBudW0xID0gMDsKCQlpbnQgbnVtMiA9IDA7CgkJaW50IHQxWzEwXSA9IHsgMCB9OwoJCWludCB0MlsxMF0gPSB7IDAgfTsKCQlmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykgewoJCQlpZiAoY2hlY2tbaV0gPT0gMSkgewoJCQkJdDFbc2l6ZTFdID0gaTsKCQkJCXNpemUxKys7CgkJCX0KCQkJZWxzZSB7CgkJCQl0MltzaXplMl0gPSBpOwoJCQkJc2l6ZTIrKzsKCQkJfQoJCX0KCgoKCQkJY291dCA8PCBzaXplMSA8PCAiICAgICAiIDw8IHNpemUyIDw8IGVuZGw7CgkJCWZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKSB7CgkJCQljb3V0IDw8IGNoZWNrW2ldIDw8ICIgIjsKCQkJfQoJCQljb3V0IDw8IGVuZGw7CgkJZm9yIChpbnQgaSA9IDA7IGkgPD0gc2l6ZTE7IGkrKykgewoJCQlmb3IgKGludCBqID0gMDsgaiA8PSBzaXplMTsgaisrKSB7CgkJCQludW0xICs9IGFyclt0MVtpXV1bdDFbal1dOwoJCQkJbnVtMiArPSBhcnJbdDJbaV1dW3QyW2pdXTsKCQkJfQoJCX0KCQlpZiAobWlubiA+IGFicyhudW0xIC0gbnVtMikpCgkJCW1pbm4gPSBhYnMobnVtMSAtIG51bTIpOwoKCQljb3V0IDw8IGNudCA8PCBlbmRsOwoJCXJldHVybjsKCX0KCWVsc2UgewoJCWZvciAoaW50IGkgPSBzdGFydDsgaSA8IG47IGkrKykgewoJCQljbnQrKzsKCQkJY2hlY2tbaV0gPSAxOwoJCQlzb2x2ZShzdGFydCArIDEpOwoJCQljaGVja1tpXSA9IDA7CgkJCWNudC0tOwoJCX0KCX0KCWlmIChjbnQgPT0gMCkKCQlyZXR1cm47CgoKfQoKCgoKaW50IG1haW4oKSB7Cglpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKCWNpbi50aWUoTlVMTCk7Cgljb3V0LnRpZShOVUxMKTsKCgljaW4gPj4gbjsKCWZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKSB7CgkJZm9yIChpbnQgaiA9IDA7IGogPCBuOyBqKyspIHsKCQkJaW50IG51bTsKCQkJY2luID4+IG51bTsKCQkJYXJyW2ldW2pdID0gbnVtOwoJCX0KCX0KCXNvbHZlKDApOwoJY291dCA8PCBtaW5uOwoKCglyZXR1cm4gMDsKfQ==