Minimum Water Bucket Operations

You are given a garden with m rows and n columns. Some cells of the garden contain plants. You have b water buckets available. In a single operation, one bucket can be used to water all plants in an entire row or an entire column.

Your task is to determine the minimum number of operations required to water all the plants. If the minimum number of operations needed is more than the available buckets, output -1.

Note that if there are no plants in the garden, no operation is needed, and the answer is 0.

The minimum number of operations can be computed as:

\(\min(|R|, |C|)\)

where \(R\) is the set of distinct rows containing a plant and \(C\) is the set of distinct columns containing a plant.

inputFormat

The input is given via stdin with the following format:

• The first line contains three integers m, n and b, representing the number of rows, columns, and available water buckets respectively.
• The second line contains an integer p that denotes the number of plants in the garden.
• The following p lines each contain two integers, representing the row and column positions of a plant.

Rows and columns are 1-indexed.

outputFormat

Output a single integer to stdout – the minimum number of water bucket operations required to water all plants, or -1 if it is not possible to do so with the available buckets.

## sample

5 5 3
4
1 2
2 2
4 4
5 1

3