Minimizing Photographed Grid Cells

Our satellite has just discovered an alien civilization on a distant planet and obtained a low‐resolution image of a square region on that planet. In this image, n points of interest (POIs) have been identified, numbered from 0 to n-1. The image represents a grid of m × m unit squares. The rows and columns of the grid are numbered from 0 to m-1 (top-to-bottom and left-to-right, respectively), and a square in row s and column t is denoted by (s, t). The i-th point of interest is located in square (r_i, c_i) (a square may contain multiple POIs).

The satellite is in a fixed orbit which happens to pass right above the grid’s main diagonal (i.e. the line segment connecting the top‐left and bottom‐right corners). It can take high–resolution photographs of square regions satisfying the following conditions:

• The photographed region must be a square.
• Both of the square’s opposite corners (interpreted as its main diagonal) must lie on the grid’s main diagonal. In other words, if a photo covers the squares from (a, a) to (b, b) (with 0 ≤ a ≤ b < m), then it is valid.
• Every grid square is either completely inside or completely outside the photographed region.

The satellite may take at most k high–resolution photos. Although a square may be captured by more than one photo, data from a given grid square is transmitted only once. Therefore, we must choose at most k squares (photos) such that:

• Every grid square that contains at least one point of interest is photographed at least once.
• The total number of grid squares which are photographed (i.e. the union of all photographed regions) is minimized.

For an interest point located at (r, c), define

$L=\min(r,c)$ and $R=\max(r,c)$. For a valid photo covering grid squares from (a, a) to (b, b), a point (r,c) is covered if and only if $a\le L$ and $b\ge R$.

Thus, each POI imposes a requirement: it must be covered by at least one photo whose corresponding interval on the main diagonal covers the interval $[L, R]$. The minimal such photo for a set of POIs is a square spanning from $a=\min\{L_i\}$ to $b=\max\{R_i\}$, with an area of $(b-a+1)^2$.

Note that if the required intervals of two POIs overlap then they must be covered by the same photo if one wishes to avoid extra coverage; if they are separated (i.e. there is a gap between them) they may be covered by different photos. In fact, one may first merge all overlapping POI intervals into clusters. Suppose after merging we obtain p disjoint clusters with cluster i having boundaries $[a_i,b_i]$. Then, if we cover clusters i through j by a single photo, its cost (i.e. number of grid squares) is $$\bigl(b_j-a_i+1\bigr)^2.$$

Your task is to choose at most k valid photos (which, if needed, must cover one or more consecutive clusters) so that every POI is covered and the total number of photographed grid squares is minimized. Output this minimum possible number.

inputFormat

The first line contains three integers: m (m is the grid size), n (the number of points of interest), and k (the maximum number of photos the satellite can take). Following this, there are n lines. The i-th of these lines contains two integers r_i and c_i (0 ≤ r_i, c_i < m), indicating the grid coordinates of the i-th point of interest.

outputFormat

Output a single integer: the minimum possible number of grid squares that are photographed (i.e. the size of the union of all photos) that still ensures every grid square containing at least one point of interest is photographed at least once.

sample

5 1 1
2 3

4