The Avaricious ISP

Time limit1sMemory limit128 MB

Summary

Choose two disjoint disks over weighted points to maximize the product of the covered weight sums.

Level: Hard8 of 10
Topics: Geometry, Sorting, Two pointers
Solved: No attempts yet

Problem

You run an internet service provider that charges by traffic. Your network manager insists on building the network from exactly two wireless antennas joined by one underground cable. Each antenna covers a circle centered on itself and you may pick the radius freely. No point of the plane may be covered by both antennas, because a device sitting where the two coverage areas overlap is confused to death.

Potential customers sit at known points of the plane. A customer joins the network if one of the two antennas covers her. Customer $i$ has a traffic desire $d_i$ . When customers $i$ and $j$ are both covered, the daily traffic between them is $d_i \times d_j$ .

The only traffic you can measure is the traffic that passes through the underground cable, that is, the traffic between pairs of customers attached to different antennas. Choose the position and the radius of both antennas so that this traffic is as large as possible.

Input

The input holds several test cases. The first line of each test case has one integer $N$ ( $1 \le N \le 200$ ), the number of potential customers. Each of the next $N$ lines has the traffic desire $d_i$ ( $1 \le d_i \le 200$ ) followed by the coordinates $x_i$ , $y_i$ ( $-10^6 \le x_i, y_i \le 10^6$ ) of one potential customer, all integers. The input ends with a line containing a single 0.

In every test case, no three potential customers lie on one straight line.

Output

For each test case, print one line with the largest traffic that can pass through the underground cable when you choose the best position and radius for each antenna.

Examples2

Example 1

Input

2
5 0 0
4 1 1
4
2 -100 -100
3 100 -100
4 -100 100
5 100 100
0

Expected output

20
48

Example 2
Input
```
3
1 0 0
2 4 0
3 0 3
0
```
Expected output
```
9
```