{"raw_statement":[{"iden":"problem statement","content":"#nck { width: 30px; height: auto; }There are $N$ cities in a two-dimensional plane. The coordinates of the $i$\\-th city is $(x_i, y_i)$. Initially, the amount of water stored in the $i$\\-th city is $a_i$ liters.\nSnuke can carry any amount of water from a city to another city. However, water leaks out a bit while he carries it. If he carries $l$ liters of water from the $s$\\-th city to the $t$\\-th city, only $max(l-d_{s,t}, 0)$ liters of water remains when he arrives at the destination. Here $d_{s,t}$ denotes the (Euclidean) distance between the $s$\\-th city and the $t$\\-th city. He can perform arbitrary number of operations of this type.\nSnuke wants to maximize the minimum amount of water among the $N$ cities. Find the maximum $X$ such that he can distribute at least $X$ liters of water to each city."},{"iden":"constraints","content":"*   $1 ≤ N ≤ 15$\n*   $0 ≤ x_i, y_i, a_i ≤ 10^9$\n*   All values in the input are integers.\n*   No two cities are at the same position."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$x_1$ $y_1$ $a_1$\n:\n$x_N$ $y_N$ $a_N$"},{"iden":"sample input 1","content":"3\n0 0 10\n2 0 5\n0 5 8"},{"iden":"sample output 1","content":"6.500000000000\n\nThe optimal solution is to carry $3.5$ liters of water from the 1st city to the 2nd city. After the operation, both the 1st and the 2nd cities will have $6.5$ liters of water, and the 3rd city will have $8$ liters of water."},{"iden":"sample input 2","content":"15\n335279264 849598327 822889311\n446755913 526239859 548830120\n181424399 715477619 342858071\n625711486 448565595 480845266\n647639160 467825612 449656269\n160714711 336869678 545923679\n61020590 573085537 816372580\n626006012 389312924 135599877\n547865075 511429216 605997004\n561330066 539239436 921749002\n650693494 63219754 786119025\n849028504 632532642 655702582\n285323416 611583586 211428413\n990607689 590857173 393671555\n560686330 679513171 501983447"},{"iden":"sample output 2","content":"434666178.237122833729"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}