题目描述

在平面直角坐标系上，有 $n$ 个不同的点。任意两个不同的点确定了一条直线。请求出所有斜率存在的直线按斜率从大到小排序后，第 $k$ 条直线的斜率为多少。

为了避免精度误差，请输出斜率向下取整后的结果。（例如：$\lfloor 1.5 \rfloor = 1$，$\lfloor -1.5 \rfloor = -2$）。

输入格式

第一行，包含两个正整数 $n$ 和 $k$。
接下来 $n$ 行，每行包含两个整数 $x_i, y_i$，表示每个点的横纵坐标。

输出格式

输出一行，包含一个整数，表示第 $k$ 大的斜率向下取整的结果。

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

2

提示

【样例说明】

符合要求的直线的斜率分别为 $-3, -\frac{1}{2}, \frac{2}{3}, 1, 2, \frac{5}{2}$ 。

【数据规模和约定】

令 $M$ 为所有斜率存在的直线的数量 。

对于 $10 \%$ 的数据，$1 \le n \le 10$。
对于 $20 \%$ 的数据，$1 \le n \le 100$，$|x_i|, |y_i| \le {10}^3$。
对于 $30 \%$ 的数据，$1 \le n \le 1000$。
对于 $40 \%$ 的数据，$1 ≤ n ≤ 5000$。
对于另 $20 \%$ 的数据，满足 $k = 1$ 。
对于另 $20 \%$ 的数据，满足 $1 \le x_i, y_i \le {10}^3$。
对于 $100 \%$ 的数据，$1 \le n \le 100000$，$1 \le k \le M$，$|x_i|, |y_i| \le {10}^8$。