Job Assignment
    One problem comes up when we are trying to assign jobs about GDCPC'2003 to staffs. Because some of them complain that the tasks assigned to them are so bother. This emotion will lead to very bad effect in sequence. So we try to satisfy every staff as possible as we can. At first , we make an investigation to get the information about staffs' attitude towards every task. And then we evaluate each attitude as a point (a positive integer number not larger than 100). The higher the point is , the more the staff is satisfied. Because the staffs are very busy. they have only a little leisure time to finish the task. So we just assign one task to one person, of course , one task can not be assigned to different persons. Now we give you all the points and hope you can help us to assign the tasks to make the sum of the points which correspond the assignment is maximum.

Input
  Input will contain several test case.The first line of each test case only contains one integer number n(1<=n<=100). N is the number of staffs also is the number of tasks. and then , the following N lines describe staffs's attitude. each line contains n positive integer nmbers. the jth number in the ith line describes ith staff's attitude to the jth task

Output
  for each test case you shold output one line, and just one number in this line. the number is the maximum

Sample Input:
2
10 90
80 100
3
50 60 70
70 75 80
80 90 100
0

Program Assign_Mpq;

Const Maxn=100;

var
  n,Answer:longint;
  lx,ly:array[1..Maxn] of integer;
  sx,sy:array[1..Maxn] of boolean;
  cx,cy:array[1..Maxn] of integer;
  g:array[1..Maxn,1..Maxn] of integer;

procedure init;
var
  i,j:integer;
begin
  for i:=1 to n do
  begin
    for j:=1 to n do read(g[i,j]);
    readln;
  end;
end;

function Find(k:integer):boolean;
var
  i:integer;
begin
  sx[k]:=true;
  for i:=1 to n do
    if (Not sy[i]) and (lx[k]+ly[i]=g[k,i]) then
    begin
      sy[i]:=true;
      if (cy[i]=0) or (Find(cy[i])) then
      begin
        cx[k]:=i;
        cy[i]:=k;
        exit(true);
      end;
    end;
  exit(false);
end;

procedure KM;
var
  i,j,k,Min:integer;
begin
  fillchar(lx,sizeof(lx),0);
  fillchar(ly,sizeof(ly),0);
  fillchar(cx,sizeof(cx),0);
  fillchar(cy,sizeof(cy),0);
  for i:=1 to n do
    for j:=1 to n do
      if lx[i]<g[i,j] then
        lx[i]:=g[i,j];

  for k:=1 to n do
    if cx[k]=0 then
      while true do
      begin
        fillchar(sy,sizeof(sy),0);
        fillchar(sx,sizeof(sx),0);
        if Find(k) then break;
        Min:=Maxint;
        for i:=1 to n do
          if sx[i] then
            for j:=1 to n do
              if Not sy[j] then
                if (lx[i]+ly[j]-g[i,j]<Min) then Min:=lx[i]+ly[j]-g[i,j];

       for i:=1 to n do
          if sx[i] then dec(lx[i],Min);
        for i:=1 to n do
          if sy[i] then inc(ly[i],Min);
      end;

  Answer:=0;
  for i:=1 to n do
    inc(Answer,g[i,cx[i]]);
  writeln(Answer);
end;

begin
assign(input,'Assign.in'); reset(input);
assign(output,'Assign.out'); rewrite(output);
  readln(n);
  while n<>0 do
  begin
    init;
    KM;
    readln(n);
  end;
close(input); close(output);
end.