ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

USU Personal Contest 2003

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. Pictures

Time limit: 1.0 second
Memory limit: 64 MB
Artist Ivanov (not the famous Ivanov who painted "Christ's apparition to people", but one of the many namesakes) once managed to rent inexpensively an excellent studio. Alas, as he soon discovered, the inexpensiveness was caused by objective reasons. A murder happened long ago in the house where he rented the room, and now the ghost living in the house each night renews blood spots on the walls of all the rooms. Ivanov's studio did not escape this damnation.
Nevertheless, being a creative person, Ivanov quickly found a simple solution to the problem. He decided to paint one or two pictures and hang them on the (single) wall where the spots appear each night so that the spots would be covered by the pictures. Of course, he does not want to spend too much time doing this work. That is why he plans to use not more than two pictures and wants the total area of the pictures to be minimal.
All the blood spots are circles. Each picture has a rectangular form with sides parallel to the axes, and the minimally possible size of a picture in each of the dimensions is 100 millimeters. If it is necessary to paint two pictures, then they should be hanged to the wall without overlaying. Each spot must be covered by exactly one picture.

Input

The first line contains the number of the spots N, 0 < N ≤ 1000. Each of the next N lines contains the description of the corresponding spot. A spot is described by three positive integers; they are the radius of the spot and the Cartesian coordinates of the center of the spot. Everything is measured in millimeters and all these numbers do not exceed 10000.

Output

Output the minimal total area (in square millimeters) of the pictures (not more than two) necessary to cover all the spots.

Sample

inputoutput
3
50 50 50
50 250 50
10 150 250
40000
Problem Author: Alexander Petrov (text — Leonid Volkov)
Problem Source: Ural State University Personal Programming Contest, March 1, 2003
To submit the solution for this problem go to the Problem set: 1245. Pictures