#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
static const int NV = 256;
typedef int flow;
typedef int cost;
typedef int vert;
typedef vert edge;
typedef vector<edge> edges;
typedef vector<edges> graph;
typedef flow flow_graph[NV][NV];
typedef cost cost_graph[NV][NV];
static const flow FLOW_INF = 0x7FFFFFFF;
static const cost COST_INF = 0x7FFFFFFF;
// edges(bidi), capacity, cost(s.t. C[x][y]=-C[y][x]) per 1 flow, src, dst
pair<cost,flow> mincostFlow(graph& G, flow_graph F, cost_graph C, vert S, vert D)
{
int N = G.size();
cost total_cost = 0;
flow total_flow = 0;
vector<cost> h(N, 0); // potential
for(cost RF=FLOW_INF; RF>0; ) // residual flow
{
// Dijkstra -- find the min-cost path
vector<cost> d(N, COST_INF); d[S] = 0;
vector<vert> prev(N, -1);
typedef pair<cost, pair<vert,vert> > cedge;
priority_queue< cedge, vector<cedge>, greater<cedge> > Q;
Q.push( cedge(0, make_pair(S,S)) );
while( !Q.empty() ) {
cedge e = Q.top(); Q.pop();
if( prev[e.second.second] >= 0 )
continue;
prev[e.second.second] = e.second.first;
vert u = e.second.second;
for(int i=0; i<G[u].size(); ++i) {
vert v = G[u][i];
cost r_cost = C[u][v] + h[u] - h[v];
if( F[u][v] > 0 && d[v] > d[u]+r_cost )
Q.push( cedge(d[v]=d[u]+r_cost, make_pair(u,v)) );
}
}
if( prev[D] < 0 )
break; // Finished
// As much as possible
flow f = RF;
for(vert u=D; u!=S; u=prev[u])
f = min(f, F[prev[u]][u]);
RF -= f;
total_flow += f;
for(vert u=D; u!=S; u=prev[u])
{
total_cost += f * C[prev[u]][u];
F[prev[u]][u] -= f;
F[u][prev[u]] += f;
}
// Update the potential
for(vert u=0; u<N; ++u)
h[u] += d[u];
}
return make_pair(total_cost, total_flow);
}
class MarblesRegroupingHard { public:
int minMoves(vector <string> boxes)
{
const int NB = boxes.size();
vector< vector<int> > bb(NB);
for(int i=0; i<boxes.size(); ++i)
{
stringstream sin(boxes[i]);
for(int v; sin>>v; )
bb[i].push_back(v);
}
const int NC = bb[0].size();
graph G(NB+NC+3);
flow_graph F = {};
cost_graph C = {};
for(int i=0; i<NB; ++i) {
G[0].push_back(2+i);
G[2+i].push_back(0);
F[0][2+i] = 1;
}
for(int i=0; i<NC; ++i) {
G[2+NB+i].push_back(1);
G[1].push_back(2+NB+i);
F[2+NB+i][1] = 1;
}
{
G[2+NB+NC].push_back(1);
G[1].push_back(2+NB+NC);
F[2+NB+NC][1] = NB-NC;
}
for(int i=0; i<NB; ++i)
for(int j=0; j<NC; ++j) {
G[2+i].push_back(2+NB+j);
G[2+NB+j].push_back(2+i);
F[2+i][2+NB+j] = 1;
int c = 0;
for(int k=0; k<NB; ++k) if(k!=i)
c += bb[k][j];
C[2+i][2+NB+j] = c;
C[2+NB+j][2+i] = -c;
}
for(int i=0; i<NB; ++i) {
G[2+i].push_back(2+NB+NC);
G[2+NB+NC].push_back(2+i);
F[2+i][2+NB+NC] = 1;
}
pair<cost,flow> ff = mincostFlow(G, F, C, 0, 1);
return ff.first;
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
bool ok = (Expected == Received);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, MarblesRegroupingHard().minMoves(boxes));}
int main(){
CASE(0)
string boxes_[] = {"0"};
vector <string> boxes(boxes_, boxes_+sizeof(boxes_)/sizeof(*boxes_));
int _ = 0;
END
CASE(1)
string boxes_[] = {"77 97","8 0"};
vector <string> boxes(boxes_, boxes_+sizeof(boxes_)/sizeof(*boxes_));
int _ = 77;
END
CASE(2)
string boxes_[] = {"6 97 7","73 45 0","67 45 63"};
vector <string> boxes(boxes_, boxes_+sizeof(boxes_)/sizeof(*boxes_));
int _ = 170;
END
CASE(3)
string boxes_[] = {"97 94 0 99","1 72 46 45","0 10 47 75","0 92 76 20","2 25 98 22"};
vector <string> boxes(boxes_, boxes_+sizeof(boxes_)/sizeof(*boxes_));
int _ = 559;
END
CASE(4)
string boxes_[] = {"38 0 0 45 77 61 0 0 8 87 65 53 0 2",
"0 97 79 37 70 0 69 35 95 11 75 96 77 29",
"39 32 0 24 63 22 91 71 0 63 92 59 12 0",
"34 0 0 71 88 13 60 56 0 22 29 89 81 53",
"69 95 65 0 94 98 84 37 0 87 16 0 58 18",
"82 0 36 88 0 54 82 40 6 0 34 44 80 2",
"33 58 7 95 83 87 0 0 79 35 0 51 22 84",
"7 0 30 57 33 4 0 26 44 55 67 31 88 42",
"62 58 62 93 91 0 1 0 44 23 95 0 55 57",
"35 8 22 26 76 0 78 54 0 46 42 0 0 64",
"93 54 58 0 89 89 0 0 57 0 98 3 24 0",
"9 0 0 23 82 18 0 46 0 0 94 84 19 18",
"78 12 6 45 0 80 16 69 59 76 35 0 66 0",
"0 68 77 13 15 0 52 72 0 0 18 65 23 0",
"0 0 73 53 0 95 91 44 27 96 85 0 99 85",
"93 29 4 89 27 44 27 17 21 6 0 8 3 91",
"0 46 73 94 60 59 15 50 18 75 74 88 46 93",
"0 0 0 94 93 26 21 83 54 62 0 89 59 77",
"32 98 0 44 34 38 56 20 0 61 29 94 52 57",
"52 60 0 22 0 5 38 0 50 98 12 75 0 81",
"23 0 41 18 36 87 49 32 62 43 22 74 0 97",
"0 0 30 79 16 73 61 0 75 51 64 13 45 0",
"11 0 14 2 0 1 2 16 84 37 95 45 48 33",
"10 0 0 35 0 85 28 76 99 74 76 32 52 8",
"60 0 96 0 95 26 59 13 0 0 44 42 97 48",
"34 7 77 25 91 85 35 78 32 99 7 29 18 15",
"61 50 43 22 42 63 64 50 9 94 42 22 21 33",
"58 0 41 10 16 0 27 67 83 27 14 37 98 47",
"37 60 60 76 71 2 84 32 27 39 82 84 0 94",
"15 98 69 82 36 66 0 97 62 39 0 65 62 67",
"0 41 0 43 0 0 94 0 0 58 0 0 27 33",
"53 90 71 91 85 0 32 86 40 60 11 0 99 28",
"79 62 0 0 79 0 14 62 87 76 35 0 70 0",
"0 40 73 48 0 63 0 0 63 5 30 18 47 51",
"75 6 58 69 33 57 66 0 12 0 46 0 65 10"};
vector <string> boxes(boxes_, boxes_+sizeof(boxes_)/sizeof(*boxes_));
int _ = 18618;
END
/*
CASE(5)
string boxes_[] = ;
vector <string> boxes(boxes_, boxes_+sizeof(boxes_)/sizeof(*boxes_));
int _ = ;
END
CASE(6)
string boxes_[] = ;
vector <string> boxes(boxes_, boxes_+sizeof(boxes_)/sizeof(*boxes_));
int _ = ;
END
*/
}
// END CUT HERE