Beetles

Time limit1sMemory limit128 MB

Summary

Given n segments, find the smallest axis-aligned square that contains at least k of them entirely, with boundary counted as inside.

Level: Hard8 of 10
Topics: Binary search, Geometry, Sorting, Sliding window
Solved: No attempts yet

Problem

Beetles live on a large, square meadow. Each beetle spends its whole life walking back and forth along a segment between two points it has chosen.

You want to catch at least $k$ beetles. To do this you will build one square fence and set it down on the meadow; the fence's sides must be parallel to the edges of the meadow (that is, an axis-aligned square). Since you never know where a beetle currently is on its segment, a beetle is guaranteed to be caught only if its entire segment lies inside the fence (the boundary counts as inside). A beetle pinned under the fence's border also counts as caught.

Find the side length of the smallest square fence that can be placed so that at least $k$ beetles are guaranteed to be caught, no matter where on their segments the beetles happen to be.

Input

The first line contains two integers $n$ and $k$ separated by a single space ( $1 \le k \le n \le 10\,000$ ). Here $n$ is the number of beetles and $k$ is how many you need to catch.

Each of the next $n$ lines describes one beetle's route with four integers $x_1, y_1, x_2, y_2$ separated by single spaces ( $0 \le x_1, y_1, x_2, y_2 \le 1\,000\,000\,000$ ). The endpoints of that beetle's walking segment are $(x_1, y_1)$ and $(x_2, y_2)$ . A coordinate $(x, y)$ denotes the point that is $x$ away from the western edge and $y$ away from the southern edge of the meadow.

Output

Print a single integer: the side length of the smallest fence that meets the requirement.

Examples2

Example 1
Input
```
4 2
1 0 3 1
0 2 1 4
4 2 2 3
2 1 1 2
```
Expected output
```
2
```
Example 2
Input
```
1 1
0 0 3 4
```
Expected output
```
4
```