발사하는 페이저

당신은 우주선의 함장이다. 지금껏 마주친 적 중 가장 사나운 적에게 몰래 다가갔다. 적의 기함이 당신을 발견하기 전에 대형 페이저 대포로 기함을 공격할 계획이다. 실수할 여지가 없으니 한 발은 완벽해야 한다.

페이저 충전을 시작했고, 자료실에서 기함의 방 배치도를 꺼냈다. 당신은 적 바로 위에 있으며, 배치도는 방들을 나타내는 2차원 지도다. 각 방은 x축과 y축에 평행한 변을 가진 직사각형이고, 어떤 두 방도 겹치지 않는다. 한 점에서도 맞닿지 않는다.

페이저 빔은 점 $(x, y)$와 각도 $\vartheta$로 설정한다. 빔은 $(x, y)$에서 출발해 $\vartheta$ 방향으로 거리 $\ell$만큼 나아가며, 닿는 방마다 큰 피해를 준다. 목표는 한 번의 발사로 가능한 한 많은 방을 맞히는 것이다.

충전은 거의 끝났고, 남은 일은 최적의 설정을 고르는 것뿐이다. 생각보다 어려운 문제다. 충전이 끝나기까지 10초가 남아 있으니, 이 문제를 푸는 프로그램을 직접 작성하기로 했다.

첫 줄에 정수 $r$과 $\ell$이 주어진다 ($1 \le r \le 15$, $1 \le \ell \le 1000$). $r$은 기함의 방 개수이고, $\ell$은 페이저 발사 거리다.

이어서 $r$개의 줄이 주어지며, 각 줄에는 정수 $x_1$, $y_1$, $x_2$, $y_2$가 있다 ($0 \le x_1 < x_2 \le 1000$, $0 \le y_1 < y_2 \le 1000$). 각 줄은 왼쪽 아래 모서리가 $(x_1, y_1)$이고 오른쪽 위 모서리가 $(x_2, y_2)$인 방을 뜻한다.

한 번의 페이저 빔으로 맞힐 수 있는 방의 최대 개수를 한 줄에 출력한다. 빔이 방에 닿기만 해도 맞힌 것으로 센다.

답은 수치적으로 안정적이라고 가정해도 된다. 즉 모든 방을 네 방향으로 $10^{-6}$만큼 넓혀도 답은 바뀌지 않는다.