Cell Phone Antenna

A straight highway is modeled as the line $y = 0$. A single antenna is to be built somewhere on this highway. The antenna has a range of $1000$ meters: it serves every house whose Euclidean distance to the antenna is at most $1000$.

Each house is described by its location $(x, y)$ and its number of inhabitants $n$. Choose the position of the antenna on the highway so that the total number of inhabitants living in houses within range is as large as possible.

Report that maximum number of inhabitants.

The first line contains the number of test cases $T$. Each test case has the following format:

• A line with an integer $h$ with $0 < h \le 1000$: the number of houses.
• $h$ lines follow, each containing three integers $x$, $y$, $n$ with $-10^4 \le x, y \le 10^4$ and $0 \le n \le 100$: the location $(x, y)$ of a house and its number of inhabitants $n$.

The highway is the line $y = 0$.

For each test case, print a single line containing one integer: the greatest number of inhabitants living in houses within range of the antenna (at Euclidean distance at most $1000$), when the antenna is placed at the best possible position along the highway.