Line Sweep

You have been coding so much that your room turned dusty. Sweep it before your parents find out.

The room is a grid with $N$ rows and $M$ columns. Each cell either holds a piece of furniture or is empty and has to be swept. At least one cell is empty.

You clean with a linear broom. A broom of length $X$ covers $X$ consecutive cells of one column. A single sweep means putting the broom down and then pushing it horizontally by any distance, and that distance may be 0. During the whole sweep the broom stays completely inside the room, and all $X$ cells it covers are empty at every moment. Every cell the broom passes over during the sweep loses its dust.

A longer broom is better, so you buy the longest broom that can still sweep the whole room. The room is completely swept once every empty cell belongs to at least one sweep. After the broom length is fixed, you also want the number of sweeps to be as small as possible.

The first line contains the number of rows $N$, the number of columns $M$, and the number of pieces of furniture $F$ ($1 \le N \le 2000$, $1 \le M \le 2000$, $1 \le F < NM$).

Each of the next $F$ lines contains the row $r$ and the column $c$ of one piece of furniture ($1 \le r \le N$, $1 \le c \le M$). No two pieces of furniture share the same coordinates.

Print the length of the longest broom you can buy on the first line.

Print the minimum number of sweeps needed to sweep every empty cell with that broom on the second line.