Have you ever heard of Pandaren Brewmaster? He is a famous neutral hero in the RTS game Warcraft ¢ó: The Frozen Throne, a game many of you may have played. Hailing from the secretive Pandaren Empire, the mighty brewmasters travel the world in search of exotic ales and the finest brewed spirits. These affable warriors rarely seek out danger or trouble, preferring instead to spend their time concocting new and tasty beverages for any brave enough to imbibe them. However, if attacked, the laughing brewmasters bring all of their pandaren agility and ferocity to bear! They are peerless warriors and world class drinkers all in one!
Pandaren Brewmaster is one of the most useful among all TFT heroes. He is especially preferred by Night Elf players, for he is a very effective "fleshy shield", and has two fantastic area-damage skills. His LV6 ultimate skill ---- "Storm, Earth and Fire" is also pretty cool, though he doesn't often have much opportunity to reach LV6.
In this problem, we are going to focus on one of his area-damage skills ---- Drunken Haze. The figure below is an introduction to it.
This skill is used to drench enemy units in alcohol. Its "Area of Effect" is 20, as indicated above. It means that this skill affects enemy units inside a circle whose diameter is 20. Now, suppose that you've encountered many enemy units in a game, and you're going to cast Drunken Haze on them. Each enemy unit has a Power Point; it may vary from unit to unit. Since Drunken Haze affect units in a quite limited area, you want to select position of the circle such that the enemy units surrounded by the circle has the maximum total Power Point.
Wanna become a TFT expert? Try to solve this problem and apply it next time you summon the Pandaren Brewmaster in your game!
Oh, by the way, many TFT fans are not satisfied with the area of effect of the Drunken Haze, which, they argue, is much too small. As a result, Blizzard Entertainment might make corresponding adjustments in the following TFT versions. In order to prepare for further TFT versions and make this problem a little harder, let's assume that the area of effect is a circle of diameter 500, rather than 20.
A little note: Your program must be very efficient to meet the time limit of this problem.
The input consists of a series of data sets, followed by a line containing a single character "0", which indicates the end of input and should not be processed. Each data set begins with a line containing an integer N, denoting the number of enemy units you've encountered. Each of the following N lines contains three integers X, Y and P. X and Y describe the coordinate of the enemy unit, and P is the Power Point of the corresponding unit.
You may assume that 1 ¡Ü N ¡Ü 300, -5000 ¡Ü X, Y ¡Ü 5000, 0 ¡Ü P ¡Ü 10000. An enemy unit right on border of a circle is considered to be INSIDE the circle.
For each data set in the input, first print the data set number, starting from 1. Then output a line containing "The maximum affected Power Point is K.", where K is the maximum Power Point of all enemy units affected by Drunken Haze.
Print a blank line after each data set.
See the sample output below for the correct output format.
7 0 0 20 3 4 7 -220 100 29 2 0 9 1 0 24 -500 0 88 4 -6 12 0Sample Output
Data set #1: The maximum affected Power Point is 137.