Description

Our satellite has just discovered an alien civilization by observing a distant planet. We have also obtained a low-resolution photo of a square area on that planet. The photo shows many signs of intelligent life. Experts have identified $n$ points of interest in the photo. These points are numbered from $0$ to $n-1$. Now we want to take some high-resolution photos that include all $n$ points of interest.

The satellite has divided the area in the low-resolution photo into a grid made of $m \times m$ unit squares. The rows and columns of the grid are consecutively numbered from $0$ to $m-1$ (from top to bottom and from left to right). We use coordinates $(s,t)$ to denote the cell in row $s$ and column $t$. The $i$-th point of interest is located in cell $(r_i,c_i)$. Each cell may contain any number of points of interest.

The satellite moves along a fixed orbit, and it happens to pass directly above the main diagonal of this grid. The main diagonal is the line segment connecting the top-left corner and the bottom-right corner of the grid. The satellite can take a high-resolution photo of any area, but it must satisfy the following conditions:

• The photographed area must be a square.
• Both diagonals of this square (note: you may understand this as the main diagonal) must lie on the main diagonal of the grid.
• Each cell in the grid must be either completely inside the photographed area or completely outside it.

The satellite can take at most $k$ high-resolution photos.

After photographing, the satellite will transmit the high-resolution data for every photographed area to the ground station (whether or not the area contains points of interest). Although a cell may be photographed multiple times, the data for each photographed cell will be transmitted only once.

Therefore, we must choose at most $k$ square areas to photograph, and ensure that:

• Every cell that contains at least one point of interest is photographed at least once.
• The number of cells photographed at least once is minimized.

Your task is to find the minimum possible number of cells that are photographed at least once.

Input Format

• Line $1$: integers $n$ (the number of points of interest), $m$ (the number of rows in the grid, also the number of columns), and $k$ (the maximum number of high-resolution photos the satellite can take).
• Line $2+i$ ($0 \le i \le n-1$): integers $r_i$ and $c_i$. $r$ and $c$ are two arrays of length $n$ describing the coordinates of the cells that contain points of interest. For $0 \le i \le n-1$, the $i$-th point of interest is located in the cell with coordinates $(r_i,c_i)$.

Output Format

• One line: the minimum total number of cells that are photographed at least once (the photos must cover all points of interest).

5 7 2
0 3
4 4
4 6
4 5
4 6

25

2 6 2
1 4
4 1

16

Hint

Subtasks

In all subtasks, $1 \le k \le n$.

Translated by ChatGPT 5