Maximizing Columns with Row Reordering

You are given an \( n \times n \) matrix \( a \). You have \( q \) independent queries. In each query, you are given a value \( v \). Before each query, you are allowed to arbitrarily reorder the elements within each row (each row can be permuted independently).

Your task is to maximize the number of columns such that the maximum value in that column is at least \( v \). In other words, after reordering the rows, count the maximum possible number of columns for which at least one element in the column is \( \ge v \).

Note: The reordering is performed separately for each query.

Approach Hint: For a fixed query \( v \), in each row count the number of elements that are \( \ge v \). Since each row’s good elements can cover at most one column each, you want to choose the maximum number \( X \) (where \( 0 \le X \le n \)) such that it is possible to cover \( X \) columns. A necessary and sufficient condition is that \( \sum_{i=1}^{n} \min(\text{count}_i, X) \ge X \), where \( \text{count}_i \) is the number of good elements (i.e. \( \ge v \)) in row \( i \).

Your goal is to output the maximum possible number of columns for each query.

inputFormat

The first line contains two integers \( n \) and \( q \) \( (1 \le n \le \text{appropriate limits},\; 1 \le q) \), representing the dimensions of the matrix and the number of queries.

The next \( n \) lines each contain \( n \) integers, representing the matrix \( a \).

The following \( q \) lines each contain an integer \( v \), representing a query.

outputFormat

For each query, output a single integer on a new line: the maximum number of columns that can have a column maximum \( \ge v \) after an optimal row reordering.

sample

3 3
3 1 4
1 5 9
2 6 5
4
5
7

3
3
1