Problem: The crowdedness of the discotheque would never stop our friends from having fun, but a bit more spaciousness won't hurt, will it?

The discotheque can be seen as an infinite xy-plane, in which there are a total of n dancers. Once someone starts moving around, they will move only inside their own movement range, which is a circular area Ci described by a center (xi, yi) and a radius ri. No two ranges' borders have more than one common point, that is for every pair (i, j) (1 ≤ i < j ≤ n) either ranges Ci and Cj are disjoint, or one of them is a subset of the other. Note that it's possible that two ranges' borders share a single common point, but no two dancers have exactly the same ranges.

Tsukihi, being one of them, defines the spaciousness to be the area covered by an odd number of movement ranges of dancers who are moving. An example is shown below, with shaded regions representing the spaciousness if everyone moves at the same time.

<image>

But no one keeps moving for the whole night after all, so the whole night's time is divided into two halves — before midnight and after midnight. Every dancer moves around in one half, while sitting down with friends in the other. The spaciousness of two halves are calculated separately and their sum should, of course, be as large as possible. The following figure shows an optimal solution to the example above.

<image>

By different plans of who dances in the first half and who does in the other, different sums of spaciousness over two halves are achieved. You are to find the largest achievable value of this sum.

Input

The first line of input contains a positive integer n (1 ≤ n ≤ 1 000) — the number of dancers.

The following n lines each describes a dancer: the i-th line among them contains three space-separated integers xi, yi and ri ( - 106 ≤ xi, yi ≤ 106, 1 ≤ ri ≤ 106), describing a circular movement range centered at (xi, yi) with radius ri.

Output

Output one decimal number — the largest achievable sum of spaciousness over two halves of the night.

The output is considered correct if it has a relative or absolute error of at most 10 - 9. Formally, let your answer be a, and the jury's answer be b. Your answer is considered correct if <image>.

Examples

Input

5
2 1 6
0 4 1
2 -1 3
1 -2 1
4 -1 1


Output

138.23007676


Input

8
0 0 1
0 0 2
0 0 3
0 0 4
0 0 5
0 0 6
0 0 7
0 0 8


Output

289.02652413

Note

The first sample corresponds to the illustrations in the legend.

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Div2_418D {

	public static void main(String[] args) throws IOException {
		new Div2_418D().execute();
	}

	int numC;
	Circle[] circles;

	ArrayList<Integer>[] chldn;

	double[][] dp;

	@SuppressWarnings("unchecked")
	void execute() throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		numC = Integer.parseInt(reader.readLine());

		circles = new Circle[numC + 1];
		Event[] events = new Event[numC * 2 + 1];

		for (int i = 1; i <= numC; i++) {
			StringTokenizer inputData = new StringTokenizer(reader.readLine());
			circles[i] = new Circle(Integer.parseInt(inputData.nextToken()), Integer.parseInt(inputData.nextToken()),
					Integer.parseInt(inputData.nextToken()));
			events[i * 2 - 1] = new Event(i, BEGIN);
			events[i * 2] = new Event(i, END);
		}
		reader.close();

		Arrays.sort(events, 1, events.length);

		int[] parent = new int[numC + 1];
		chldn = new ArrayList[numC + 1];
		for (int i = 1; i <= numC; i++) {
			chldn[i] = new ArrayList<Integer>();
		}

		// sweep line
		TreeSet<ExtPoint> actExt = new TreeSet<ExtPoint>();

		for (int eI = 1; eI <= numC * 2; eI++) {
			Event cEvent = events[eI];
			int cCircle = cEvent.sInd;

			ExtPoint cTop = new ExtPoint(cCircle, TOP);
			ExtPoint cBottom = new ExtPoint(cCircle, BOTTOM);

			if (cEvent.state == BEGIN) {
				ExtPoint higher = actExt.higher(cTop);
				if (higher != null && higher.oInd != 0) {
					if (higher.half == TOP) {
						parent[cCircle] = higher.oInd;
						chldn[higher.oInd].add(cCircle);
					} else {
						parent[cCircle] = parent[higher.oInd];
						if (parent[higher.oInd] != 0) {
							chldn[parent[higher.oInd]].add(cCircle);
						}
					}
				}
				actExt.add(cTop);
				actExt.add(cBottom);
			} else {
				actExt.remove(cTop);
				actExt.remove(cBottom);
			}
		}

		dp = new double[2][numC + 1];

		double ans = 0;
		for (int i = 1; i <= numC; i++) {
			if (parent[i] == 0) {
				computeDP(i, 1);
				ans += dp[ADD][i];
			}
		}
		System.out.printf("%.10f", ans);
	}

	final int ADD = 1;
	final int SUB = 0;

	void computeDP(int cV, int dep) {
		for (int chld : chldn[cV]) {
			computeDP(chld, dep + 1);
		}

		int eff1 = SUB;
		int eff2 = (dep & 1) ^ 1;

		// case 1: cV belongs to part 1
		double sum1 = -circles[cV].area;
		for (int chldn : chldn[cV]) {
			sum1 += dp[ADD][chldn];
		}

		// case 2: cV belongs to part 2
		double sum2 = eff2 == ADD ? circles[cV].area : -circles[cV].area;
		for (int chldn : chldn[cV]) {
			sum2 += dp[SUB][chldn];
		}
		dp[SUB][cV] = Math.max(sum1, sum2);

		// case 1: cV belongs to part 1
		eff1 = ADD;
		eff2 = dep & 1;

		// case 1: cV belongs to part 1
		sum1 = circles[cV].area;
		for (int chldn : chldn[cV]) {
			sum1 += dp[SUB][chldn];
		}

		// case 2: cV belongs to part 2
		sum2 = eff2 == ADD ? circles[cV].area : -circles[cV].area;
		for (int chldn : chldn[cV]) {
			sum2 += dp[ADD][chldn];
		}
		dp[ADD][cV] = Math.max(sum1, sum2);
	}

	final int BEGIN = -1;
	final int END = 1;

	class Event implements Comparable<Event> {
		int sInd;
		int state;

		Event(int sInd, int state) {
			this.sInd = sInd;
			this.state = state;
		}

		public int compareTo(Event oth) {
			Circle tSponsor = circles[sInd];
			Circle oSponsor = circles[oth.sInd];
			int tP = tSponsor.x + state * tSponsor.r;
			int oP = oSponsor.x + oth.state * oSponsor.r;
			if (tP != oP) {
				return tP < oP ? -1 : 1;
			}

			if (state != oth.state) {
				return state == END ? -1 : 1;
			}

			if (tSponsor.r != oSponsor.r) {
				return tSponsor.r > oSponsor.r ? -1 : 1;
			}
			return Integer.compare(sInd, oth.sInd);
		}
	}

	class Circle {
		int x;
		int y;
		int r;
		double area;

		Circle(int x, int y, int r) {
			this.x = x;
			this.y = y;
			this.r = r;
			area = Math.PI * (long) r * r;
		}
	}

	final int TOP = 1;
	final int BOTTOM = -1;

	// the ExtPoint class holds either the circle's topmost or bottommost point
	// sorting of the ExtPoint class is done very tactically: regular sorting except when the circles to whom the
	// extreme points belong don't overlap, in which case the extreme points are sorted by the relative positions of
	// the corresponding centers
	// this method of sorting effectively enables us to "straighten" an otherwise irregular placement of circles
	class ExtPoint implements Comparable<ExtPoint> {
		int oInd;
		int half;

		ExtPoint(int oInd, int half) {
			this.oInd = oInd;
			this.half = half;
		}

		public int compareTo(ExtPoint oth) {
			Circle tOwner = circles[oInd];
			Circle oOwner = circles[oth.oInd];
			long xDist = tOwner.x - oOwner.x;
			long yDist = tOwner.y - oOwner.y;
			long rSum = tOwner.r + oOwner.r;
			if (xDist * xDist + yDist * yDist >= rSum * rSum) { // circles do not overlap
				return Integer.compare(tOwner.y, oOwner.y);
			}

			long tExt = tOwner.y + half * tOwner.r;
			long oExt = oOwner.y + oth.half * oOwner.r;

			if (tExt != oExt) {
				return tExt < oExt ? -1 : 1;
			}

			if (half == TOP && oth.half == TOP) {
				return Integer.compare(tOwner.r, oOwner.r);
			} else if (half == BOTTOM && oth.half == BOTTOM) {
				return -Integer.compare(tOwner.r, oOwner.r);
			} else if (half == TOP) {
				return -1;
			} else {
				return 1;
			}
		}
	}
}