P5896 [IOI 2016] aliens

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.

- 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)$.

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

**Subtasks** In all subtasks, $1 \le k \le n$. | Subtask | Score | $n \le$ | $m \le$ | Other constraints | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $4$ | $5$ | $100$ | $k=n$ | | $2$ | $12$ | $500$ | $10^3$ | $r_i=c_i$ | | $3$ | $9$ | $500$ | $10^3$ | None | | $4$ | $16$ | $4 \times 10^3$ | $10^6$ | None | | $5$ | $19$ | $5 \times 10^4$ | $10^6$ | $k \le 100$ | | $6$ | $40$ | $10^5$ | $10^6$ | None | Translated by ChatGPT 5