Problem Description

Our satellite has recently observed an alien civilization on a distant planet. We have also obtained a low-resolution photograph of a square region of this planet, which contains numerous signs of intelligent life. Experts have identified $n$ points of interest on this photograph, numbered from $0$ to $n-1$. We now wish to take high-resolution photographs that include all $n$ points of interest.

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

The satellite orbits in a fixed path directly above the main diagonal of this grid. The main diagonal is the line segment connecting the top-left corner to the bottom-right corner of the grid. The satellite can take high-resolution photographs of any region, but must adhere to the following conditions:

• The photographed region must be a square.
• Both diagonals of this square must be contained within the main diagonal of the grid.
• Each unit square in the grid is either entirely within the photographed region or entirely outside it.
  The satellite can take a maximum of $k$ high-resolution photographs.

Once the satellite has completed its photography, it will transmit the high-resolution photographs of each region to the ground station (regardless of whether these regions contain points of interest). Although a unit square may be photographed multiple times, the data from each unit square will only be transmitted once.

Therefore, we must select up to $k$ square regions for photography, ensuring that:

• Every unit square containing at least one point of interest is photographed at least once.
• The number of unit squares photographed at least once is minimized.

Your task is to find the minimum number of unit squares that could be photographed.

Input Format

• The first line: integers $n$ representing the number of points of interest, $m$ representing the number of rows (and columns) in the grid, and $k$ representing the maximum number of high-resolution photographs the satellite can take.
• The $2+i$-th line (for $0 \le i \le n-1$): integers $r_i$ and $c_i$. $r$ and $c$ are arrays of length $n$ describing the coordinates of the unit squares containing points of interest. For $0 \le i \le n-1$, the $i$-th point of interest is located at the unit square with coordinates $(r_i, c_i)$.

Output Format

• A single line: the minimum total number of unit squares that must be photographed at least once (these photographs must cover all points of interest).

Sample Input and Output

Input Sample #1

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

Output Sample #1

25

Input Sample #2

2 6 2
1 4
4 1

Output Sample #2

16

Notes/Hints

Subtasks

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

见题面 Input 部分

见题面 Output 部分