시험 좌석 고르기

시험에서는 어떤 자리에 앉느냐가 준비만큼이나 중요할 때가 있습니다. 다른 학생의 답안을 몰래 보고 싶다면, (1) 많은 학생의 답안을, 그것도 (2) 성적이 좋은 학생의 답안을 볼 수 있는 자리를 고르고 싶을 것입니다. 여기에는 분명한 상충 관계가 있습니다. 가까운 답안일수록 더 잘 보이지만, 다른 학생에게 시야가 완전히 가로막히기도 하므로 가장 좋은 자리를 찾는 것은 결코 쉬운 문제가 아닙니다.

모든 좌석은 $d \times d$ 격자의 정수 좌표 위에 있으며, $(1, 1)$부터 $(d, d)$까지 번호가 매겨집니다. 각 좌표 $(x, y)$에는 실력 $s_{x,y} \ge 0$ 과 어깨너비 $w_{x,y} \in [0, 1/2]$ 를 가진 학생이 앉아 있습니다. 비어 있는 좌석은 $s_{x,y} = 0$, $w_{x,y} = 0$ 으로 나타냅니다.

좌석 $(x, y)$ 에 앉으면 "앞쪽"만 볼 수 있습니다. 즉 $y' < y$ 인 좌석 $(x', y')$ 의 답안만 볼 수 있습니다. 좌표 $(x, y)$ 의 학생은 $(x - w_{x,y},\, y)$ 에서 $(x + w_{x,y},\, y)$ 까지 이어지는 직선 선분으로 모형화되며, 어떤 학생의 선분도 뚫고 볼 수 없습니다. 모든 학생은 답안을 자신의 한가운데 $(x, y)$ 에 둡니다.

엄밀히 말하면, $(x, y)$ 에 앉아 있을 때 $(x', y')$ 의 답안을 볼 수 있으려면 $y' < y$ 이고, $(x, y)$ 에서 $(x', y')$ 로 그은 직선이 $(x', y')$ 의 학생을 제외한 다른 어떤 학생도 지나가지 않아야 합니다. 직선이 어떤 학생 선분의 끝(가장자리)을 정확히 지나가는 경우에도 그 학생을 지나간 것으로 봅니다.

시력에는 한계가 있어 멀리 있는 답안일수록 알아보기 어렵습니다. 시력이 $E$ 이고 학생이 (유클리드) 거리 $D > E$ 에 있으면 아무것도 알아볼 수 없습니다. 거리 $D \le E$ 이면 그 학생 답안의 $1 - D/E$ 만큼을 읽을 수 있습니다. 당신이 얻는 총이득은, 답안을 볼 수 있는 모든 학생에 대해 그들의 실력에 읽을 수 있는 비율을 곱한 값을 모두 더한 것입니다. 마지막으로, 당연히 비어 있는 좌석에만 앉을 수 있습니다.

첫 줄에는 데이터 집합의 개수 $K \ge 1$ 이 주어집니다. 이어서 $K$ 개의 데이터 집합이 다음 형식으로 주어집니다.

각 데이터 집합의 첫 줄에는 두 수, 곧 교실의 정수 크기 $d \le 100$ 과 시력 $E > 0$ (실수) 이 주어집니다.

그다음에는 $d^2$ 개의 줄이 이어지며, $d(y - 1) + x$ 번째 줄은 위치 $(x, y)$ 에 앉은 학생을 설명합니다. 각 줄에는 두 수 $s$, $w$, 곧 학생의 실력과 어깨너비가 주어집니다. 둘 다 음이 아닌 실수이며, 어깨너비는 최대 $1/2$ 입니다. 각 데이터 집합에는 비어 있는 좌석이 적어도 하나 있음이 보장됩니다.

각 데이터 집합마다 먼저 Data Set x: 를 한 줄에 출력합니다. 여기서 $x$ 는 데이터 집합의 번호입니다(1부터 시작). 그다음 줄에, 그 교실에서 가장 좋은 빈 좌석에 앉았을 때 얻을 수 있는 최대 총이득을 소수 둘째 자리까지 반올림하여 출력합니다.