Exam Seating

Sometimes the choice of exam seat matters at least as much as your preparation. If you wanted to copy from classmates, you would want a seat from which you can see the exams of (1) many students who are (2) doing well in the class. There is a clear tradeoff: you read a nearby exam better, and sometimes your view is completely blocked by other students, so finding the best seat is a real problem.

All seats sit at integer points of a $d \times d$ grid, numbered from $(1, 1)$ to $(d, d)$. At each location $(x, y)$ sits a student with skill $s_{x,y} \ge 0$ and shoulder width $w_{x,y} \in [0, 1/2]$. An unoccupied seat is modeled as $s_{x,y} = 0$ and $w_{x,y} = 0$.

Sitting at seat $(x, y)$ you can only see "forward", meaning you can only copy from seats $(x', y')$ with $y' < y$. A student at $(x, y)$ is modeled as the straight segment from $(x - w_{x,y},\, y)$ to $(x + w_{x,y},\, y)$, and you can never see through any student segment. Each student keeps the exam in the middle, at $(x, y)$.

Formally, sitting at $(x, y)$ you can possibly see an exam at $(x', y')$ if $y' < y$ and the straight line from $(x, y)$ to $(x', y')$ does not pass through any student other than the one at $(x', y')$. If the line passes exactly through the edge of a student's segment, it counts as passing through that student.

Your eyesight is limited, so farther exams are harder to read. If your eyesight is $E$ and a student sits at (Euclidean) distance $D > E$, you cannot read anything. At distance $D \le E$ you can read a fraction $1 - D/E$ of that student's exam. Your total benefit is the sum, over all students whose exams you can see, of their skill weighted by the fraction you can read. Finally, you may only sit in an empty seat.

The first line contains an integer $K \ge 1$, the number of data sets. It is followed by $K$ data sets of the following form.

The first line of a data set contains two numbers: the integer classroom size $d \le 100$ and your eyesight $E > 0$ (a floating-point number).

This is followed by $d^2$ lines; line $d(y - 1) + x$ describes the student at position $(x, y)$. Each such line contains two numbers $s$ and $w$: the student's skill and shoulder width. Both are non-negative floating-point numbers, and the width is at most $1/2$. Each data set is guaranteed to contain at least one empty seat.

For each data set, first print Data Set x: on a line by itself, where $x$ is the data set number (starting from 1). Then print the maximum total benefit you can obtain at the best empty seat in the room, rounded to two decimals.