#K15976. Optimal Crop Allocation

    ID: 24476 Type: Default 1000ms 256MiB

Optimal Crop Allocation

Optimal Crop Allocation

You are given f fields and c crop types. Each field has a capacity and each crop type requires a specific amount of space. A field i with size \(S_i\) can only be used to plant a crop type j if the crop's space requirement \(R_j\) satisfies \(R_j \leq S_i\). Each field can accommodate at most one crop and each crop type can only be planted once. Your task is to determine the maximum number of distinct crop types that can be planted across the fields.

In other words, find the maximum matching between the fields and the crops under the constraint:

[ R_j \leq S_i \quad \text{for the assigned crop } j \text{ to field } i. ]

The input contains several datasets. Each dataset starts with two integers, f and c, which represent the number of fields and the number of crop types respectively. It is followed by f integers representing the field sizes and then c integers representing the space required for each crop type. A dataset with f = 0 and c = 0 indicates the end of input.

inputFormat

The input is read from the standard input (stdin) and consists of several datasets. Each dataset is structured as follows:

  • The first line contains two integers: f (the number of fields) and c (the number of crop types).
  • The second line contains f integers representing the sizes of the fields.
  • The third line contains c integers representing the space required for each crop type.

The input terminates with a line where both f and c are 0. Each dataset (except the terminating one) should be processed, and the corresponding result printed in order.

outputFormat

For each dataset, output a single integer on a new line representing the maximum number of different crop types that can be planted under the given constraints.

## sample
3 4
10 8 5
3 6 4 2
8 3
20 15 10 25 30 10 20 15
10 20 15
2 2
5 15
5 10
0 0
3

3 2

</p>