问题描述

农夫约翰有N(1<=N<=1000)只奶牛，每只奶牛住在B(1<=B<=20)个奶牛棚中的一个。当然，奶牛棚的容量有限。有些奶牛对它现在住的奶牛棚很满意，有些就不太满意了。

农夫约翰想要重新安排这些奶牛，使得奶牛的满意度尽可能相同，尽管有可能这意味者所有的奶牛都不喜欢新分配的奶牛棚。

每只奶牛都按顺序给出她喜欢的奶牛棚。在某个分配方案中，一只奶牛的满意度等于她对她的奶牛棚的评价等级。你的工作是找出一种分配方案使得没有奶牛棚超出它的容量，而且奶牛给分配到的奶牛棚的评价等级的相对范围（即分配到的等级最高的奶牛棚和等级最低的奶牛棚之间的差值）尽可能的小。

输入格式

第一行：两个用空格隔开的整数，N和B

第二行到第N+1行：每一行都有B个用空格隔开的正整数，它们恰好是1到B的一个排列。第i+1行的第一个整数是第i只奶牛的首选牛棚的编号，该行的第二个整数是第i只奶牛的第二选择，等等。

第N+2行：B个用空格隔开的整数，分别表示这B个奶牛棚的容量。这些数的和保证至少为N。

输出格式

一个整数，被分配到的牛棚等级的最小相对差值。

样例输入(stead.in)

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

样例输出(stead.out)

2

样例说明

每个奶牛都被安排在它的第一选择或第二选择：1号牛棚安排1号奶牛和5号奶牛，2号牛棚安排2号奶牛，3号牛棚安排4号奶牛，4号牛棚安排3号奶牛和6号奶牛。