Description

On the 2D Cartesian plane, there are $n$ distinct points. Any two distinct points determine a line. Among all lines whose slopes are defined, sort them by slope in descending order and find the slope of the $k$-th line.

To avoid precision errors, please output the floor of the slope. (For example: $\lfloor 1.5 \rfloor = 1$, $\lfloor -1.5 \rfloor = -2$.)

Input Format

The first line contains two positive integers $n$ and $k$.
Each of the next $n$ lines contains two integers $x_i, y_i$, the coordinates of a point.

Output Format

Output one line containing an integer: the floor of the $k$-th largest slope.

4 1
-1 -1
2 1
3 3
1 4

2

Hint

[Sample Explanation]

The slopes of the lines that meet the requirement are $-3, -\frac{1}{2}, \frac{2}{3}, 1, 2, \frac{5}{2}$.

[Constraints]

Let $M$ be the number of lines whose slopes are defined.

• For $10\%$ of the testdata, $1 \le n \le 10$.
• For $20\%$ of the testdata, $1 \le n \le 100$, $|x_i|, |y_i| \le 10^3$.
• For $30\%$ of the testdata, $1 \le n \le 1000$.
• For $40\%$ of the testdata, $1 \le n \le 5000$.
• For another $20\%$ of the testdata, $k = 1$.
• For another $20\%$ of the testdata, $1 \le x_i, y_i \le 10^3$.
• For $100\%$ of the testdata, $1 \le n \le 100000$, $1 \le k \le M$, $|x_i|, |y_i| \le 10^8$.

Translated by ChatGPT 5