long hongrois(int n, long d[n][N], int a[n])  // return min \sum_i d[i][a[i]] 
{ long x[n], y[n], mi[n], s;
  int b[n], i0, i, j;
  long f(int i,int j) { if((lu)i>=(lu)n || (lu)(j)>=(lu)n) printf("raté i=%d j=%d\n",i,j); return d[i][j]-x[i]-y[j]; }
  for(i=n;i--;) a[i]=b[i]=-1, x[i]=y[i]=~0lu>>1;
  for(j=n;j--;) for(i=n;i--;) y[j]=min(y[j],d[i][j]);
  for(i=n;i--;) for(j=n;j--;) x[i]=min(x[i],d[i][j]-y[j]);
  for(i0=n;i0--;)
  { int xm[n], ym[n], p[n], ip=0;
    for(j=n;j--;) mi[j]=f(i0,j), xm[j]=ym[j]=-1;
    xm[p[ip++]=i0]=n;
    while(j<0) if(ip)
     for(i=p[--ip],j=n;j--;)
      if(ym[j]>=0) ; else
      if(f(i,j)) mi[j]=min(mi[j],f(i,j)); else
      if(b[j]<0) break; else
      xm[p[ip++]=b[j]]=j, ym[j]=i;
               else  
    { for(s=~0lu>>1,j=n;j--;) if(ym[j]<0) s=min(s,mi[j]);
      for(j=n;j--;) if(ym[j]<0) y[j]+=s, mi[j]-=s;
      for(i=n;i--;) if(xm[i]<0) x[i]-=s;
      for(j=n;j--;) if(ym[j]<0 && !mi[j])
       { for(i=n;xm[--i]<0 || f(i,j);) ;
         if(b[j]<0) break; else
         xm[p[ip++]=b[j]]=j, ym[j]=i;
       }
    }
    for(;b[a[i]=j]=i,i!=i0;i=ym[j]) j=xm[i];
  }
  for(s=0,i=n;i--;) s+=d[i][a[i]]; 
  for(i=n;i--;) for(j=n;j--;) d[i][j]-=x[i]+y[j];
  for(i=n;i--;) for(j=n;j--;) if(d[i][j]<0) printf("f(%d,%d)=%ld\n",i,j,d[i][j]), exit(1);
  for(i=n;i--;) if((lu)a[i]>=(lu)n) printf("a[%d]=%d\n",i,a[i]), exit(1);
  for(j=n;j--;) if((lu)b[j]>=(lu)n) printf("b[%d]=%d\n",j,a[j]), exit(1);
  for(i=n;i--;) if(a[b[i]]!=i) printf("a[b[%d]=%d]=%d\n",i,b[i],a[b[i]]), exit(1);
  for(i=n;i--;) if(d[i][a[i]]) printf("f(%i,a[%i])=%ld\n",i,i,d[i][a[i]]), exit(1);
  return s;
}