Artemis

Time limit2sMemory limit128 MB

Summary

Given N points with distinct x and y, find the axis-parallel rectangle with two opposite corners on points that contains at least T points and the fewest total points.

Level: Hard8 of 10
Topics: Prefix sum, Binary search, Sorting, Combinatorics
Solved: No attempts yet

Problem

Zeus gave Artemis, goddess of the wilderness, a rectangular plot of land to grow a forest. The left edge of the plot lies on the positive $y$ -axis, the bottom edge on the positive $x$ -axis, and the lower-left corner of the plot is the origin $(0, 0)$ . Zeus told Artemis to plant trees only on integer coordinate points inside the plot.

Artemis likes the forest to look natural, so she planted the trees in such a way that the line connecting any two trees is never parallel to the $x$ -axis or the $y$ -axis. In other words, all trees have distinct $x$ -coordinates and all trees have distinct $y$ -coordinates.

From time to time Zeus asks Artemis to cut down trees for him. The trees must be cut according to the following rules:

At least $T$ trees, the number Zeus requires, are cut.
To build a future football pitch, Artemis cuts every tree inside a single rectangular region and no tree outside of it.
The sides of this rectangle are parallel to the $x$ -axis and the $y$ -axis.
Two opposite corners of the rectangle must lie on trees, and those two corner trees are cut as well.

Because Artemis loves the trees, she wants to satisfy these conditions while cutting as few trees as possible. Since there may be several ways to pick the pair of trees that serve as the two opposite corners, report the minimum number of trees that Artemis must cut.

Input

The first line contains the number of trees in the forest, $N$ . The second line contains $T$ , the minimum number of trees that must be cut. Each of the following $N$ lines describes one tree with two space-separated integers $X$ and $Y$ : the $x$ -coordinate and the $y$ -coordinate of that tree.

Output

Print, on a single line, the minimum number of trees that Artemis must cut. That is, among all axis-parallel rectangles whose two opposite corners both lie on trees and that contain at least $T$ trees (corners included), print the smallest number of trees any such rectangle contains.

Constraints

$1 < N \le 20000$
$0 \le X, Y \le 64000$
$1 < T \le N$
All trees have distinct $x$ -coordinates and all trees have distinct $y$ -coordinates.
It is guaranteed that at least one valid rectangle exists.

Examples3

Example 1
Input
```
3
2
1 1
2 3
5 6
```
Expected output
```
2
```
Example 2
Input
```
2
2
1 1
2 2
```
Expected output
```
2
```
Example 3
Input
```
5
3
1 1
2 2
3 3
4 4
5 5
```
Expected output
```
3
```