Description

The rabbits decide to station some soldiers in their castle.

Given the coordinates of $n$ points and a circular obstacle in the castle whose center is at the origin, the rabbits want to choose $k$ rabbits such that, for every pair of chosen rabbits, the line determined by them does not intersect the circle.

The rabbits want to know the maximum number of rabbits they can choose.

Input Format

The first line contains two integers $n$ and $r$, denoting the number of rabbits and the radius of the circle.

Then $n$ lines follow. Each line contains two integers $x_i$ and $y_i$, representing the coordinates of the $i$-th rabbit.

It is guaranteed that every rabbit lies strictly outside the obstacle, and that for any two rabbits, the line through them is not tangent to the circle.

Output Format

Output a single integer on one line, representing the maximum number of rabbits that can be chosen.

6 3
0 6
-7 -4
-3 -2
7 -5
-2 3
8 -3

4

Hint

Sample 1 Explanation

Choosing rabbits $1, 2, 6, 4$ works.

Constraints

• For $10\%$ of the testdata, $1\leq n\leq 20$.
• For $30\%$ of the testdata, $1\leq n\leq 100$.
• For $100\%$ of the testdata, $1\leq n\leq 2000$ and $1\leq r,x_i,y_i \leq 5000$.

Translated by ChatGPT 5