시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 40 8 7 17.949%

문제

플라위 : 반가워! 내 이름은 플라위, 노란 꽃 플라위야!! 너 이 지하세계는 처음인가 보구나, 그렇지? 이런, 정말 정신 없겠네. 이곳이 어떤 곳인지 누군가 알려줘야겠는데! 작고 힘없는 나라도 알려줘야겠네. 준비됐니? 간다!

플라위 : 하트 모양이 보이지? 저게 네 영혼이야. 네 존재의 정수지! 네 영혼은 약하지만, LV를 많이 올리면 강해질 수 있어. LV가 뭐냐고? 바로, LOVE지, 물론! LOVE가 좀 필요한 것 같은데, 그렇지?

플라위 : 걱정하지 마, 내가 좀 나눠줄게! 작고 하얀... “친절 알갱이”로 서로 나누지. 움직여! 친절을 최대한 많이 받는 거야!

플라위는 총 N개의 친절 알갱이를 뿌렸다. 이 알갱이들은 모두 1의 속도로 일직선으로 움직인다. 한편, 당신의 영혼도 임의의 방향으로 최대 1의 속도로 움직일 수 있다. 당신은 1, 0.314 등의 임의의 속도로 움직일 수 있으며, 가만히 있을 수도 있다. 하지만 영혼은 특정 직사각형 영역 밖으로 나갈 수 없다. 당신의 영혼은 처음에 (0, 0) 위치에 있으며, [-XM, -YM] ~ [XM, YM] 범위 안에서만 움직일 수 있다.

각각의 친절 알갱이는 당신의 영혼과 닿으면 사라진다. 따라서 당신은 최대 N개의 친절 알갱이를 모을 수 있다. 친절 알갱이의 정보가 주어질 때, 당신이 최대 몇 개의 친절 알갱이를 모을 수 있는지 구하는 프로그램을 작성하라. 단, 당신의 영혼과 친절 알갱이는 점으로 간주한다.

입력

첫 번째 줄에는 친절 알갱이의 수 N(1≤N≤18), 영혼이 도달할 수 있는 범위를 나타내는 두 정수 XM, YM (1 ≤ XM, YM ≤ 500)이 주어진다. 두 번째 줄부터 N개의 줄에는 각각의 친절 알갱이의 정보에 해당하는 4개의 정수 Xst, Yst, Xto, Yto(-1,000≤Xst, Yst, Xto, Yto≤1,000)가 주어진다. 친절 알갱이의 처음 위치는 (Xst, Yst)이며, 이 알갱이는 (Xto, Yto)를 향해 일직선으로 움직인다. 친절 알갱이는 (Xto, Yto)를 지난 이후에도 계속 움직인다. (Xst, Yst)와 (Xto, Yto)는 서로 다른 점이며, 출발점이 원점으로 들어오는 경우는 없다.

출력

첫번째 줄에 당신이 모을 수 있는 친절 알갱이의 수의 최댓값을 출력한다.

예제 입력

5 10 8
-12 24 0 0
-8 28 0 0
0 30 0 0
8 28 0 0
12 24 0 0

예제 출력

5

예제 입력 2

4 93 93
93 93 93 -93
93 -93 -93 -93
-93 -93 -93 93
-93 93 93 93

예제 출력 2

2

힌트