Problem 2: Indraneel's Orchard, *(Madhavan Mukund, CMI)*

Indraneel has a square orchard
in which there are special places to plant trees one metre
apart in either direction. These designated positions form an
*N* × *N* grid of points, which are labelled from
(1,1) on the bottom left corner to (*N*,*N*) on the top
right corner.

The orchard currently has *M* trees scattered around the
grid. Indraneel now realizes that he needs to provide a horizontal
road *K* metres wide from left to right across the field. The
road has to be aligned with the grid points. In other words, the
lower and upper boundaries of the road should both lie along a row of
tree planting positions. Any tree that lies on the road will have to
be cut, including trees that are on the upper and lower boundary of
the road.

Indraneel is free to choose the position of this road. Your task is to help him find the minimum number of trees that need to be cut to lay the road.

For instance, suppose that the orchard has 10 rows and columns
with 12 trees at the positions marked below, and the road that is to
be built is 3 metres wide. In the figure, each '.' represents a
grid point where a tree can be placed and the `T`'s represent
the actual positions of the trees.

. . . . . . . T . . . T . . . . . . . . T . . . T . . . . . . T . . . . . . . . . . . T . . . . . . . . . . . T . . . . . . . . . . T . . . T . . . . . . T . . . . . . . . . . . T . . T . . . . . . .

In this case, the best choice is to lay the road between row 4 and row 7 on the grid. This will require cutting 4 trees. Any other choice will sacrifice more trees - for instance, if the road were laid between row 2 and row 5, he would have to cut down 5 trees.

Input format

The first line of input consists of three integers, *N*,
*M* and *K*, where *N* is the number of
rows/columns of the field, *M* is the number of trees in the
field and *K* is the width of the road to be built. This is
followed by *M* lines of input, describing the locations of the
trees. Each of these *M* lines consists of two integers
*R* and *C*, 1 ≤ *R*,*C* ≤
*N*, giving the row and column number of the tree. Rows are
numbered from bottom to top and columns are numbered from left to
right.

Output format

The output should be a single integer denoting the minimum number of trees that need to be cut to lay the road.

Test data

You may assume that *N* ≤ 10^{8}, *M* ≤
10^{6} and *K* &le 10^{6}. In 70% of the
inputs, *M* ≤ 5000 and *K* &le 5000.

Example

We now illustrate the input and output formats using the example discussed above.

Sample input

10 12 3 10 8 8 1 7 2 5 6 9 2 3 1 1 3 6 4 2 10 8 5 3 8 4 7

Sample output

4

Copyright (c) IARCS 2003-2020; Last Updated: 22 Oct 2007