Equalizing Barn Happiness

Farmer John's N cows reside in B barns with limited capacities. Each cow provides her complete preference order of the barns (from most to least preferred). When a cow is assigned to a barn, her happiness is determined by the ranking of that barn in her list (with 1 being the highest). Although it might be the case that every cow ends up in a barn she dislikes, Farmer John wants to rearrange the cows so that the range of happiness levels is as small as possible.

Define the range as \(\text{range} = (\max_{i=1}^{N} r_i - \min_{i=1}^{N} r_i + 1)\), where \(r_i\) is the ranking (or position) of the barn assigned to the \(i\)th cow. In other words, if the best assignment among the cows is \(L\) (i.e. rank L) and the worst is \(H\) (i.e. rank H), then the range is \(H - L + 1\). Your task is to compute the minimum possible range such that all the cows can be assigned to barns according to their preferences and no barn exceeds its capacity.

inputFormat

The input begins with a line containing two integers \(N\) and \(B\) (\(1 \le N \le 1000\), \(1 \le B \le 20\)), representing the number of cows and the number of barns respectively.

The second line contains \(B\) integers. The \(i\)th integer is the capacity of barn \(i\).

Then follow \(N\) lines. Each of these lines contains a permutation of the numbers from 1 to \(B\), representing a cow's preference order (from her most to least preferred barn).

outputFormat

Output a single integer indicating the minimum possible range of happiness rankings among all cows after an assignment that respects barn capacities.

sample

3 3
1 2 1
1 2 3
2 1 3
1 2 3

1