infO(1) Cup 2024 Mirror - Day 2 | Lattice

For every two positive integers $N, M,$ we define $lattice(N, M)$ to be those points $(x, y)$ for which $N$ divides $x$ and $M$ divides $y$, and where $x, y$ are non-negative integers. In other words, the points of $lattice(N, M)$ can be thought of as those points reachable from $(0, 0)$ by moving a multiple of $N$ steps to the right, and a multiple of $M$ steps up. For example, $lattice(2, 3)$ looks like this.

Task

Given $K$ and a list of $P$ points $(x_1, y_1), \dots , (x_P, y_P)$ with integer coordinates in the plane, answer the following question: For how many positive integers $x$ does $lattice(x, x)$ contain at least $K$ of the $P$ points?

Input data

The first line of the input contains $P$ and $K$. The next $P$ lines contain the points $(x_i, y_i)$.

Output data

The first line of the output should contain the answer to the question.

Restrictions

• $1 \leq x_i, y_i \leq 1 \ 000 \ 000$
• $1 \leq K \leq P \leq 200 \ 000$

Example 1

stdin

3 2
1 3
3 6
4 2

stdout

1

Explanation

In the first example, only $lattice(1, 1)$ contains at least $2$ points.

Example 2

stdin

5 2
2 2
5 10
6 4
15 5
1 7

stdout

3

Explanation

Here, $lattice(1, 1)$ contains all the points, $lattice(2, 2)$ has the first and the third point and $lattice(5, 5)$ has the second and the fourth point. Below is a grid showing all the lattices. $lattice(1, 1)$ is the underlying grid, $lattice(2, 2)$ is marked by $\color{red}\text{red x’s}$, and $lattice(5, 5)$ is marked by $\color{blue}\text{blue x’s}$. The points in all three lattices are marked by $\color{purple}\text{purple x’s}$. The $P$ points in the input are marked by filled-in circles $(•)$, with the colour showing which grid they belong to: if a point is only in $lattice(1, 1)$ it is $\color{gray}\text{gray}$, if it is in $lattice(1, 1)$ and $lattice(2, 2)$ it is $\color{red}\text{red}$, and if it is in $lattice(1, 1)$ and $lattice(5, 5)$ it is $\color{blue}\text{blue}$.