3647. [USACO Feb06]稳定的牛分配

【题目描述】

农夫约翰的 N 头奶牛住在 B 个谷仓里，每个谷仓的容量有限，有的牛很喜欢现在的住所，而有的则对现在的住所非常不满意。

农夫约翰打算重新安排奶牛的住所，使得它们的幸福感尽可能的接近，哪怕这会使所有牛都对安排产生不满。

每头奶牛都给了约翰一个住所幸福感列表，被安排的谷仓在列表中的排名将直接影响牛的幸福感高低。

你需要给定一个合理的安排，使得每个谷仓安排的牛的数量不能超过容量上限，并且幸福感最高的牛和幸福感最低的牛的幸福感差距尽量的小。

换句话说，对住所最满意的牛被安排的住所在其列表中的排名和对住所最不满意的牛被安排的住所在其列表中的排名之间相差最小。

【输入格式】

第 1 行包含两个整数 N 和 B。

第 2..N+1 行，每行包含 B 个整数，第 i+1 行描述了第 i 头牛的住所幸福感列表，越靠前的住所牛越满意。

第 N+2 行，包含 B 个整数，第 i 个整数表示第 i 间谷仓的容量。

【输出格式】

输出一个整数，表示牛被安排的住所在列表上的排名的范围是多少。

例如，一共 4 头牛，3 头被安排在满意度排名 1 的谷仓，1 头被安排在满意度排名 2 的谷仓，则范围是 [1,2]，输出 2。

【样例输入】

6 4
1 2 3 4
2 3 1 4
4 2 3 1
3 1 2 4
1 3 4 2
1 4 2 3
2 1 3 2

【样例输出】

2

【数据规模与约定】

$1\leq N\leq 1000,1\leq B\leq 20$