题目描述

农夫约翰的 $N$ 头奶牛住在 $B$ 个谷仓里，每个谷仓的容量有限。每头奶牛都有一个住所幸福感列表，越靠前的谷仓，奶牛越满意。

农夫约翰打算重新安排奶牛的住所，需要满足以下条件：

1. 每个谷仓安排的牛的数量不能超过其容量上限；
2. 使得所有牛中，对住所最满意的牛的满意度排名与对住所最不满意的牛的满意度排名之间的差距尽可能小。

你需要计算这个最小的排名差距。

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

输入格式

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

接下来 $N$ 行，每行包含 $B$ 个整数，表示第 $i$ 头奶牛的住所幸福感列表（越靠前的谷仓越满意）。

再接下来一行，包含 $B$ 个整数，表示每个谷仓的容量上限。

输出格式

输出一个整数，表示最小的排名范围（即最大排名减最小排名加 1 吗？仔细看例子：如果最小排名是 1，最大排名是 2，输出的是 2，说明输出的是最大排名与最小排名的差加 1，即排名区间的长度）。

样例

输入样例：

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

样例解释

有 $6$ 头牛，$4$ 个谷仓。每头牛的偏好列表和谷仓容量已知。

可以安排得使所有牛被分配的谷仓在其偏好列表中的排名都在区间 $[1,2]$ 内，因此输出 $2$。

具体方案（一种可能）：

• 谷仓1（容量2）：分配偏好列表第1名为谷仓1的牛
• 谷仓2（容量1）：分配偏好列表第1名为谷仓2的牛
• 谷仓3（容量3）：分配偏好列表第1或第2名为谷仓3的牛
• 谷仓4（容量2）：分配偏好列表第1或第2名为谷仓4的牛

从而使最大排名为 2，最小排名为 1，差值加 1 = 2。

数据范围

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

时空限制

• 时间限制：1 秒
• 空间限制：64 MB