Indian National Olympiad in Informatics

Related:

Online Programming Contest, 15-16 September 2007

IARCS home > OLYMPIAD

Basic Division

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⁸, M ≤ 10⁶ and K &le 10⁶. 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

Sample output