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.util.*;
import java.io.*;
import java.math.BigDecimal;
import java.math.MathContext;
public class Main {
    static class Scan {
        private byte[] buf=new byte[1024];
        private int index;
        private InputStream in;
        private int total;
        public Scan()
        {
            in=System.in;
        }
        public int scan()throws IOException
        {
            if(total<0)
            throw new InputMismatchException();
            if(index>=total)
            {
                index=0;
                total=in.read(buf);
                if(total<=0)
                return -1;
            }
            return buf[index++];
        }
        public int scanInt()throws IOException
        {
            int integer=0;
            int n=scan();
            while(isWhiteSpace(n))
            n=scan();
            int neg=1;
            if(n=='-')
            {
                neg=-1;
                n=scan();
            }
            while(!isWhiteSpace(n))
            {
                if(n>='0'&&n<='9')
                {
                    integer*=10;
                    integer+=n-'0';
                    n=scan();
                }
                else throw new InputMismatchException();
            }
            return neg*integer;
        }
        public double scanDouble()throws IOException
        {
            double doub=0;
            int n=scan();
            while(isWhiteSpace(n))
            n=scan();
            int neg=1;
            if(n=='-')
            {
                neg=-1;
                n=scan();
            }
            while(!isWhiteSpace(n)&&n!='.')
            {
                if(n>='0'&&n<='9')
                {
                    doub*=10;
                    doub+=n-'0';
                    n=scan();
                }
                else throw new InputMismatchException();
            }
            if(n=='.')
            {
                n=scan();
                double temp=1;
                while(!isWhiteSpace(n))
                {
                    if(n>='0'&&n<='9')
                    {
                        temp/=10;
                        doub+=(n-'0')*temp;
                        n=scan();
                    }
                    else throw new InputMismatchException();
                }
            }
            return doub*neg;
        }
        public String scanString()throws IOException
        {
            StringBuilder sb=new StringBuilder();
            int n=scan();
            while(isWhiteSpace(n))
            n=scan();
            while(!isWhiteSpace(n))
            {
                sb.append((char)n);
                n=scan();
            }
            return sb.toString();
        }
        private boolean isWhiteSpace(int n)
        {
            if(n==' '||n=='\n'||n=='\r'||n=='\t'||n==-1)
            return true;
            return false;
        }
    }
    
    public static void sort(int arr[],int l,int r) {    //sort(arr,0,n-1);
        if(l==r) {
            return;
        }
        int mid=(l+r)/2;
        sort(arr,l,mid);
        sort(arr,mid+1,r);
        merge(arr,l,mid,mid+1,r);
    }
    public static void merge(int arr[],int l1,int r1,int l2,int r2) {
        int tmp[]=new int[r2-l1+1];
        int indx1=l1,indx2=l2;
        //sorting the two halves using a tmp array
        for(int i=0;i<tmp.length;i++) {
            if(indx1>r1) {
                tmp[i]=arr[indx2];
                indx2++;
                continue;
            }
            if(indx2>r2) {
                tmp[i]=arr[indx1];
                indx1++;
                continue;
            }
            if(arr[indx1]<arr[indx2]) {
                tmp[i]=arr[indx1];
                indx1++;
                continue;
            }
            tmp[i]=arr[indx2];
            indx2++;
        }
        //Copying the elements of tmp into the main array
        for(int i=0,j=l1;i<tmp.length;i++,j++) {
            arr[j]=tmp[i];
        }
    }
    
    public static void sort(long arr[],int l,int r) {    //sort(arr,0,n-1);
        if(l==r) {
            return;
        }
        int mid=(l+r)/2;
        sort(arr,l,mid);
        sort(arr,mid+1,r);
        merge(arr,l,mid,mid+1,r);
    }
    public static void merge(long arr[],int l1,int r1,int l2,int r2) {
        long tmp[]=new long[r2-l1+1];
        int indx1=l1,indx2=l2;
        //sorting the two halves using a tmp array
        for(int i=0;i<tmp.length;i++) {
            if(indx1>r1) {
                tmp[i]=arr[indx2];
                indx2++;
                continue;
            }
            if(indx2>r2) {
                tmp[i]=arr[indx1];
                indx1++;
                continue;
            }
            if(arr[indx1]<arr[indx2]) {
                tmp[i]=arr[indx1];
                indx1++;
                continue;
            }
            tmp[i]=arr[indx2];
            indx2++;
        }
        //Copying the elements of tmp into the main array
        for(int i=0,j=l1;i<tmp.length;i++,j++) {
            arr[j]=tmp[i];
        }
    }
    
    public static void main(String args[]) throws IOException {
        Scan input=new Scan();
        int n=input.scanInt();
        int x[]=new int[n];
        int y[]=new int[n];
        int r[]=new int[n];
        int mark[]=new int[n];
        for(int i=0;i<n;i++) {
            x[i]=input.scanInt();
            y[i]=input.scanInt();
            r[i]=input.scanInt();
        }
        sort(n,x,y,r);
        for(int i=0;i<n;i++) {
//            System.out.println(x[i]+" "+y[i]+" "+r[i]);
        }
        int cnt=1;
        for(int i=0;i<n;i++) {
            if(mark[i]!=0) {
                continue;
            }
            mark[i]=cnt;
            cnt++;
            for(int j=i+1;j<n;j++) {
//                System.out.println(i+" "+j+" "+overlap(x,y,r,i,j));
                if(overlap(x,y,r,i,j)) {
                    mark[j]=mark[i];
                }
            }
        }
        int depth[]=new int[n];
        for(int i=0;i<n;i++) {
            for(int j=i+1;j<n;j++) {
                if(overlap(x,y,r,i,j)) {
                    depth[j]++;
                }
            }
        }
        for(int i=0;i<n;i++) {
//            System.out.println(i+" "+mark[i]+" "+depth[i]);
        }
        BigDecimal ans=new BigDecimal("0");
        for(int i=1;i<cnt;i++) {
            BigDecimal gain=new BigDecimal("0");
            BigDecimal tmp=null,tmp_g=null;
            for(int j=0;j<n;j++) {
                if(mark[j]!=i) {
                    continue;
                }
                if(depth[j]%2==1) {
                    continue;
                }
                BigDecimal add=new BigDecimal("0");
                BigDecimal sub=new BigDecimal("0");
                BigDecimal gain_add=new BigDecimal("0");
                BigDecimal gain_sub=new BigDecimal("0");
                for(int k=j;k<n;k++) {
                    if(mark[k]!=i) {
                        continue;
                    }
                    if(!overlap(x,y,r,j,k)) {
                        continue;
                    }
                    if(depth[k]%2==0) {
                        add=add.add(area(r[k]), MathContext.DECIMAL64);
                        if(depth[k]-depth[j]>=2) {
                            gain_add=gain_add.add(area(r[k]), MathContext.DECIMAL64);
                        }
                    }
                    else {
                        sub=sub.add(area(r[k]), MathContext.DECIMAL64);
                        if(depth[k]-depth[j]>=1) {
                            gain_sub=gain_sub.add(area(r[k]), MathContext.DECIMAL64);
                        }
                    }
                }
                add=add.subtract(sub, MathContext.DECIMAL64);
                if(tmp==null) {
                    tmp=new BigDecimal(""+add);
                }
                gain=new BigDecimal(""+gain_sub);
                gain=gain.multiply(new BigDecimal("2"), MathContext.DECIMAL64);
                gain=gain.subtract(gain_add, MathContext.DECIMAL64);
                gain=gain.subtract(gain_add, MathContext.DECIMAL64);
//                System.out.println(gain);
                if(tmp_g==null && gain.compareTo(new BigDecimal("0"))==1) {
                    tmp_g=new BigDecimal(""+gain);
                }
                else if(tmp_g!=null){
                    if(tmp_g.compareTo(gain)==-1) {
                        tmp_g=new BigDecimal(""+gain);
                    }
                }
            }
//            System.out.println("tmp"+tmp);
            ans=ans.add(tmp, MathContext.DECIMAL64);
//            System.out.println(tmp_g);
            if(tmp_g!=null) {
                ans=ans.add(tmp_g, MathContext.DECIMAL64);
            }
        }
        System.out.println(ans);
    }
    public static void sort(int n,int x[],int y[],int r[]) {
        for(int i=0;i<n;i++) {
            for(int j=0;j<n-1;j++) {
                if(r[j]<r[j+1]) {
                    swap(x,j,j+1);
                    swap(y,j,j+1);
                    swap(r,j,j+1);
                }
            }
        }
    }
    public static void swap(int arr[],int l,int r) {
        int tmp=arr[l];
        arr[l]=arr[r];
        arr[r]=tmp;
    }
    public static boolean overlap(int x[],int y[],int r[],int indx1,int indx2) {
        long x1=x[indx1];
        long y1=y[indx1];
        long x2=x[indx2];
        long y2=y[indx2];
        long tmp1=(x1-x2)*(x1-x2);
        long tmp2=(y1-y2)*(y1-y2);
        long tmp=tmp1+tmp2;
        long r1=r[indx1];
        r1*=r[indx1];
        long r2=r[indx2];
        r2*=r[indx2];
//        System.out.println(indx1+" "+indx2+" "+tmp+" "+r1+" "+r2);
        if(tmp<=r1 || tmp<=r2) {
            return true;
        }
        return false;
    }
    public static BigDecimal area(int r) {
        BigDecimal ans=new BigDecimal(""+r);
        ans=ans.multiply(ans,MathContext.DECIMAL64);
        ans=ans.multiply(new BigDecimal(""+3.1415926535897932384626433832), MathContext.DECIMAL64);
        return ans;
    }
}