시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 66 15 11 19.298%

문제

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

플라위 : 하트 모양이 보이지? 저게 네 영혼이야. 네 존재의 정수지! 네 영혼은 약하지만, 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)는 서로 다른 점이며, 출발점이 원점으로 들어오는 경우는 없다.

출력

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

예제 입력 1

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

예제 출력 1

5

예제 입력 2

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

예제 출력 2

2