시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB0000.000%

문제

Each second Martynas catches a glimpse of the sky through his telescope expecting to see a falling star. Every time he sees a falling star he makes a wish upon it.

Martynas believes that the more falling stars he will see while making a wish, the higher the probability the wish will come true.

Calculate the largest possible number of stars Martynas can see during a glimpse through his telescope.

The sky can be modelled as an endless plane. Martynas can see an area limited by a circle with center $(0, 0)$ and radius $R$.

Before opening his telescope Martynas checked the star chart:

  • There are $N$ stars in the sky;
  • During the first glimpse the coordinates of the $i$’th star will be $a_i$, $b_i$;
  • During the second glimpse (which will take place $1$ sec. after the first one) the $i$’th star will be $c_i$, $d_i$;
  • All the stars are moving at constant speed;
  • The position of each star will change between the first and the second glimpse.

Martynas can keep looking at the stars forever.

입력

The first input line contains two numbers: the total amount of stars $N$ and the radius of the circle $R$.

Each of remaining $N$ lines contains $4$ integers each: $a_i$, $b_i$, $c_i$, $d_i$ describing the position of $i$’th star during the first and the second glimpse.

출력

The first and the only output line should contain one integer – largest possible number of stars visible through the telescope.

제한

  • $1 ≤ N ≤ 200\,000$
  • $1 ≤ R ≤ 100\,000\,000$
  • $-100\,000\,000 ≤ a_i , b_i , c_i , d_i ≤ 100\,000\,000$ (a star will move, i.e.: $(a_i , b_i) \ne (c_i , d_i)$)

서브태스크

번호배점제한
123

$-10\,000 ≤ R, a_i , b_i , c_i , d_i ≤ 10\,000$ and $b_i = d_i$ and $N ≤ 1\,000$

223

$-10\,000 ≤ R, a_i , b_i , c_i , d_i ≤ 10\,000$ and $b_i = d_i$

315

$-10\,000 ≤ R, a_i , b_i , c_i , d_i ≤ 10\,000$ and $N ≤ 1\,000$

432

$-10\,000 ≤ R, a_i , b_i , c_i , d_i ≤ 10\,000$

57

No additional constraints

예제 입력 1

3 2
-5 0 -4 0
3 0 2 0
10 0 9 0

예제 출력 1

2

During the second and the third glimpse Martynas will see only the 2nd start. During the fourth, the fifth and the sixth glimpse he will see the 1st and the 2nd stars. When glancing the seventh and the eigth time he will see only the 1st star, and from the ninth to the thirteenth time he will only see the 3rd star.

예제 입력 2

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

예제 출력 2

2

Both stars are visible during the second glimpse.

예제 입력 3

2 2
3 0 5 0
-2 1 2 1

예제 출력 3

0

This time Martynas was unlucky. One star will fly through the telescope between the first and the second glimpse, the other – between the first and the second glimpses.

채점 및 기타 정보

  • 예제는 채점하지 않는다.