description
Farmer John的N(1<=N<=1000)头奶牛分别居住在农场所拥有的B(1<=B<=20)个牛棚的某一个里。有些奶牛很喜欢她们当前住的牛棚，而另一些则讨厌再在它们现在所在的牛棚呆下去。
FJ在忍受了若干次奶牛的抱怨后，决定为所有奶牛重新安排牛棚，使最不满的那头奶牛与最高兴的奶牛的心情差异最小，即使这会让所有奶牛都更加郁闷。
每头奶牛都把她对各个牛棚的好感度从高到低排序后告诉了FJ。当然，如果一头奶牛被安排到的牛棚在她给出的列表中越靠后，她就会越郁闷。你可以认为奶牛的郁闷指数是她被分配到的牛棚在列表中的位置。奶牛们是斤斤计较的，她们无法容忍别的奶牛在自己喜欢的牛棚里快乐地生活，而自己却呆在一个自己不喜欢的牛棚里。每个牛棚都只能容纳一定数量的奶牛。FJ希望在每个牛棚都没有超出容量限制的前提下，使最郁闷和最高兴的奶牛的郁闷指数的跨度最小。
FJ请你帮他写个程序，来计算这个最小的郁闷指数跨度到底是多少。
analysis
-
二分(+)网络流，考试没读懂题少考虑了一种情况
-
对于每个牛棚，二分找出它到接下来最少第几个牛棚可以让所有牛住得下
-
这个判断用二分图匹配或者跑网络流，因为牛棚很少于是枚举也行
-
(S)和牛连流量为(1)的边，牛和牛棚连流量为(1)的边，牛棚和(T)连流量为牛棚容量的边
-
用(SAP)多快，记录最小值就好了
code
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAXN 2005
#define MAXM 50005
#define INF 1000000007
#define ll long long
#define fo(i,a,b) for (ll i=a;i<=b;++i)
#define fd(i,a,b) for (ll i=a;i<=b;--i)
#define rep(i,a) for (ll i=last[a];i;i=next[i])
using namespace std;
ll last[MAXM],next[MAXM],tov[MAXM],len[MAXM],cur[MAXM];
ll f[21],d[MAXN],gap[MAXN],a[MAXN][21];
ll n,m,S,T,tot=1,ans=INF;
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while (ch<'0' || '9'<ch){if (ch=='-')f=-1;ch=getchar();}
while ('0'<=ch && ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
inline ll min(ll x,ll y)
{
return x<y?x:y;
}
inline void link(ll x,ll y,ll z)
{
next[++tot]=last[x],last[x]=tot,tov[tot]=y,len[tot]=z;
next[++tot]=last[y],last[y]=tot,tov[tot]=x,len[tot]=0;
}
inline ll dfs(ll x,ll flow)
{
if (x==T)return flow;
ll ans=0;
for (ll i=cur[x];i;i=next[i])
{
cur[x]=i;
if (len[i] && d[tov[i]]+1==d[x])
{
ll tmp=dfs(tov[i],min(len[i],flow-ans));
ans+=tmp,len[i]-=tmp,len[i^1]+=tmp;
if (ans==flow)return ans;
}
}
cur[x]=last[x];
if (!(--gap[d[x]]))d[S]=n;
++gap[++d[x]];
return ans;
}
inline ll SAP()
{
ll flow=0;
while (d[S]<n)flow+=dfs(S,INF);
return flow;
}
inline bool judge(ll x,ll y)
{
memset(last,0,sizeof(last)),memset(next,0,sizeof(next));
memset(tov,0,sizeof(tov)),memset(len,0,sizeof(len));
memset(cur,0,sizeof(cur)),tot=1;
memset(gap,0,sizeof(gap)),memset(d,0,sizeof(d));
fo(i,1,n)link(S,i,1);fo(i,1,m)link(n+i,T,f[i]);
fo(i,1,n)fo(j,x,y)link(i,a[i][j]+n,1);
ll tmp=SAP();
return tmp==n;
}
inline ll binarysearch(ll x,ll l,ll r)
{
ll mid=(l+r)>>1;
while (l<=r)
{
mid=(l+r)>>1;
if (judge(x,mid))r=mid-1;
else l=mid+1;
}
return l;
}
int main()
{
freopen("T3.in","r",stdin);
n=read(),m=read();
fo(i,1,n)fo(j,1,m)a[i][j]=read();
fo(i,1,m)f[i]=read();
S=n+m+1,T=S+1;
fo(k,1,m)
{
ll next=binarysearch(k,k,m);
if (next<=m)ans=min(ans,next-k+1);
}
printf("%lld
",ans);
return 0;
}