题目描述

On the sphere centered at $(0, 0, 0)$ with radius $R$, there are $N$ circles. The $i$-th circle is defined as the set of intersection points between the sphere and the following plane:

• The plane passes through the point $(X_i, Y_i, Z_i)$.
• The plane is orthogonal to $\vec{v} = (X_i, Y_i, Z_i)$.

It is guaranteed that $\vec{v} \neq \vec{0}$.

It is also guaranteed that no two circles share any common point.

:::align{center}

Figure E-1: The circle defined by $(X_i, Y_i, Z_i)$ :::

We define the distance between two points on the sphere as follows:

For a path on the sphere connecting these two points, count how many of the circles the path intersects. The distance is the minimum possible value of this count over all such paths.

You may choose one point on the sphere and designate it as the Pole. Find the minimum possible value of

$$\max_{p \in \text{sphere}} \text{distance(Pole, } p \text{)} $$

输入格式

The input is given in the following format:

$$\begin{aligned} &N \ R \\ &X_1 \ Y_1 \ Z_1 \\ &X_2 \ Y_2 \ Z_2 \\ &\vdots \\ &X_N \ Y_N \ Z_N \end{aligned} $$

• $1 \leq N \leq 2000$
• $1 \leq R \leq 10^6$
• $0 < \|(X_i, Y_i, Z_i)\| < R$ ($1 \leq i \leq N$)
• No two circles share any common point.
• All input values are integers.

输出格式

Output the answer in a single line.

5 100
14 -11 -2
-54 46 8
54 -57 -12
-34 39 7
64 -74 -4

3

提示

:::align{center}

Figure E-2: Illustration of Sample Input :::