Cell Phone Antenna

Interview

Time limit1sMemory limit128 MB

Summary

Place one antenna of range 1000 on the line y=0 so that the total inhabitants of all covered houses is maximized, and report that maximum.

Level: Medium6 of 10
Topics: Geometry, Intervals, Sorting, Brute force
Solved: No attempts yet

Problem

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.

Input

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$ .

Output

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.

Examples2

Example 1

Input

2
2
100 100 20
500 500 30
3
1000 -500 4
4000 500 2
5000 -400 3

Expected output

50
5

Example 2

Input

3
1
-9999 0 42
2
-500 500 10
500 -500 20
1
0 999 1

Expected output

42
30
1