Problem: As you know, every birthday party has a cake! This time, Babaei is going to prepare the very special birthday party's cake.

Simple cake is a cylinder of some radius and height. The volume of the simple cake is equal to the volume of corresponding cylinder. Babaei has n simple cakes and he is going to make a special cake placing some cylinders on each other.

However, there are some additional culinary restrictions. The cakes are numbered in such a way that the cake number i can be placed only on the table or on some cake number j where j < i. Moreover, in order to impress friends Babaei will put the cake i on top of the cake j only if the volume of the cake i is strictly greater than the volume of the cake j.

Babaei wants to prepare a birthday cake that has a maximum possible total volume. Help him find this value.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of simple cakes Babaei has.

Each of the following n lines contains two integers ri and hi (1 ≤ ri, hi ≤ 10 000), giving the radius and height of the i-th cake.

Output

Print the maximum volume of the cake that Babaei can make. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if <image>.

Examples

Input

2
100 30
40 10


Output

942477.796077000


Input

4
1 1
9 7
1 4
10 7


Output

3983.539484752

Note

In first sample, the optimal way is to choose the cake number 1.

In second sample, the way to get the maximum volume is to use cakes with indices 1, 2 and 4.

Solution (in JAVA):

Solution:
import java.util.*;
import java.io.*;
import java.math.*;
public class hc {
	InputStream is;
	PrintWriter out;
	long mod=pow(10,9)+7;
	static int block;
	static boolean prime[];
	static long segment[];
	void solve()
	{
		int n=ni();
		pair p[]=new pair[n];
		segment=new long[4*(n+1)+1];
		for(int i=0;i<n;i++)
		{
			long r=nl();
			long h=nl();
			p[i]=new pair(r*r*h,i);
		}
		Arrays.sort(p);
	//	debug(p);
		for(int i=0;i<n;i++)
		{
			pair temp=p[i];
			long t=query(0,0,n-1,0,temp.y-1);
			update(0,0,n-1,temp.y,max(temp.x,t+temp.x));
		}
		//System.out.println(query(0,0,n-1,0,n-1));
		out.println(Math.PI*query(0,0,n-1,0,n-1));
	}
	public static long query(int n,int l,int r,int ul,int ur)
	{
		if(ul>ur)
			return 0;
		if(ul>r||ur<l)
			return	Long.MIN_VALUE;
		if(ul<=l&&ur>=r)
			return segment[n];
		int mid=(l+r)/2;
		return max(query(2*n+1,l,mid,ul,ur),query(2*n+2,mid+1,r,ul,ur));
		
	}
	public static void update(int n,int l,int r,int index,long dx)
	{
		if(l==r)
		{
			segment[n]=dx;
			return;
		}
		int mid=(l+r)/2;
		if(index<=mid)
			update(2*n+1,l,mid,index,dx);
		else
			update(2*n+2,mid+1,r,index,dx);
		segment[n]=max(segment[2*n+1],segment[2*n+2]);
	}
	static class pair implements Comparable<pair>{
		 
        long x;
        int y,k,i;
        
	pair (long x,int y){
		this.x=x;
		this.y=y;
	}
        
	public int compareTo(pair o) {
			if(this.x!=o.x)
				return	Long.compare(this.x,o.x);
			else
				return 	o.y-this.y;
	}
 
     /*   public boolean equals(Object o) {
            if (o instanceof Pair) {
                Pair p = (Pair)o;
                return p.x == x && p.y == y && p.k==k;
            }
            return false;
        }
           
 */
        @Override
        public String toString() {
            return  "("+x + " " + y +" "+k+" "+i+" )";
        }
    
    } 
	public static void prime(int n)
	{
		prime=new boolean[n+1];
		int count=0;
		for(int i=2;i*i<=n;i++)
		{
			if(prime[i])
				continue;
			for(int j=i;j*i<=n;j++)
			{
				prime[i*j]=true;
			}
		}
	}
	static class Query implements Comparable<Query>
	{
		private int l,r,in,size;	
		public Query(int l, int r,int in) 
		{ 
			this.l = l;
			this.r = r;
			this.in=in;
			this.size=l/block;
		}
		@Override
		public int compareTo(Query o) 
		{
			// TODO Auto-generated method stub
			if(this.size!=o.size)
				return this.size-o.size;
			else
				return this.r-o.r;
		}
	}
/*	static class Pair implements Comparable<Pair>{
		 
        int x,y,k,i;
        
	Pair (int x,int y,int i){
		this.x=x;
		this.y=y;
		this.i=i;
	}
        
	public int compareTo(Pair o) {
			if(this.x!=o.x)
				return	this.x/block-o.x/block;
			else
				return 	this.y-o.y;
	}
 
        public boolean equals(Object o) {
            if (o instanceof Pair) {
                Pair p = (Pair)o;
                return p.x == x && p.y == y && p.k==k;
            }
            return false;
        }
           
 
        @Override
        public String toString() {
            return  "("+x + " " + y +" "+k+" "+i+" )";
        }
    
    }*/ 
	public static int count(int num)
	{
		int count=0;
		while(num!=0)
		{
			num=num&(num-1);
			count++;
		}
		return count;
	}
	/*static long d, x, y;
	void extendedEuclid(long A, long B) {
	    if(B == 0) {
	        d = A;
	        x = 1;
	        y = 0;
	    }
	    else {
	        extendedEuclid(B, A%B);
	        long temp = x;
	        x = y;
	        y = temp - (A/B)*y;
	    }
	}
	long modInverse(long A,long M) //A and M are coprime
	{
	    extendedEuclid(A,M);
	    return (x%M+M)%M;    //x may be negative
	}*/
	public static void mergeSort(int[] arr, int l ,int r){
		if((r-l)>=1){
			int mid = (l+r)/2;
			mergeSort(arr,l,mid);
			mergeSort(arr,mid+1,r);
			merge(arr,l,r,mid);
		}
	}
	public static void merge(int arr[], int l, int r, int mid){
		int n1 = (mid-l+1), n2 = (r-mid);
		int left[] = new int[n1];
		int right[] = new int[n2];
		for(int i =0 ;i<n1;i++) left[i] = arr[l+i];
		for(int i =0 ;i<n2;i++) right[i] = arr[mid+1+i];
		int i =0, j =0, k = l;
		while(i<n1 && j<n2){
			if(left[i]>right[j]){
				arr[k++] = right[j++];
			}
			else{
				arr[k++] = left[i++];
			}
		}
		while(i<n1) arr[k++] = left[i++];
		while(j<n2) arr[k++] = right[j++];
	}
	public static void mergeSort(long[] arr, int l ,int r){
		if((r-l)>=1){
			int mid = (l+r)/2;
			mergeSort(arr,l,mid);
			mergeSort(arr,mid+1,r);
			merge(arr,l,r,mid);
		}
	}
	public static void merge(long arr[], int l, int r, int mid){
		int n1 = (mid-l+1), n2 = (r-mid);
		long left[] = new long[n1];
		long right[] = new long[n2];
		for(int i =0 ;i<n1;i++) left[i] = arr[l+i];
		for(int i =0 ;i<n2;i++) right[i] = arr[mid+1+i];
		int i =0, j =0, k = l;
		while(i<n1 && j<n2){
			if(left[i]>right[j]){
				arr[k++] = right[j++];
			}
			else{
				arr[k++] = left[i++];
			}
		}
		while(i<n1) arr[k++] = left[i++];
		while(j<n2) arr[k++] = right[j++];
	}
	    
	    public static boolean isPal(String s){
	        for(int i=0, j=s.length()-1;i<=j;i++,j--){
	                if(s.charAt(i)!=s.charAt(j)) return false;
	        }
	        return true;
	    }
	    public static String rev(String s){
			StringBuilder sb=new StringBuilder(s);
			sb.reverse();
			return sb.toString();
	    }
	    
	    public static long gcd(long x,long y){
		if(x%y==0)
			return y;
		else
			return gcd(y,x%y);
	    }
	    
	    public static int gcd(int x,int y){
		if(x%y==0)
			return y;
		else 
			return gcd(y,x%y);
	    }
	    
	    public static long gcdExtended(long a,long b,long[] x){
	        
	        if(a==0){
	            x[0]=0;
	            x[1]=1;
	            return b;
	        }
	        long[] y=new long[2];
	        long gcd=gcdExtended(b%a, a, y);
	        
	        x[0]=y[1]-(b/a)*y[0];
	        x[1]=y[0];
	        
	        return gcd;
	    }
	    
	    public static int abs(int a,int b){
		return (int)Math.abs(a-b);
	    }
	 
	    public static long abs(long a,long b){
		return (long)Math.abs(a-b);
	    }
	    
	    public static int max(int a,int b){
		if(a>b)
			return a;
		else
			return b;
	    }
	 
	    public static int min(int a,int b){
		if(a>b)
			return b;
		else 
			return a;
	    }
	    
	    public static long max(long a,long b){
		if(a>b)
			return a;
		else
			return b;
	    }
	 
	    public static long min(long a,long b){
		if(a>b)
			return b;
		else 
			return a;
	    }
	 
	    public static long pow(long n,long p,long m){
		 long  result = 1;
		  if(p==0)
		    return 1;
		if (p==1)
		    return n;
		while(p!=0)
		{
		    if(p%2==1)
		        result *= n;
		    if(result>=m)
		    result%=m;
		    p >>=1;
		    n*=n;
		    if(n>=m)
		    n%=m;
		}
		return result;
	    }
	    
	    public static long pow(long n,long p){
		long  result = 1;
		  if(p==0)
		    return 1;
		if (p==1)
		    return n;
		while(p!=0)
		{
		    if(p%2==1)
		        result *= n;	    
		    p >>=1;
		    n*=n;	    
		}
		return result;
	    }
	    public static void debug(Object... o) {
			System.out.println(Arrays.deepToString(o));
		}
	    void run() throws Exception {
			is = System.in;
			out = new PrintWriter(System.out);
			solve();
			out.flush();
		}
	   
	    public static void main(String[] args) throws Exception {
			new Thread(null, new Runnable() {
				public void run() {
					try {
						new hc().run();
					} catch (Exception e) {
						e.printStackTrace();
					}
				}
			}, "1", 1 << 26).start();
		}
	    private byte[] inbuf = new byte[1024];
		public int lenbuf = 0, ptrbuf = 0;
	 
		private int readByte() {
			if (lenbuf == -1)
				throw new InputMismatchException();
			if (ptrbuf >= lenbuf) {
				ptrbuf = 0;
				try {
					lenbuf = is.read(inbuf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (lenbuf <= 0)
					return -1;
			}
			return inbuf[ptrbuf++];
		}
	 
		private boolean isSpaceChar(int c) {
			return !(c >= 33 && c <= 126);
		}
	 
		private int skip() {
			int b;
			while ((b = readByte()) != -1 && isSpaceChar(b));
			return b;
		}
	 
		private double nd() {
			return Double.parseDouble(ns());
		}
	 
		private char nc() {
			return (char) skip();
		}
	 
		private String ns() {
			int b = skip();
			StringBuilder sb = new StringBuilder();
			while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
				sb.appendCodePoint(b);
				b = readByte();
			}
			return sb.toString();
		}
	 
		private char[] ns(int n) {
			char[] buf = new char[n];
			int b = skip(), p = 0;
			while (p < n && !(isSpaceChar(b))) {
				buf[p++] = (char) b;
				b = readByte();
			}
			return n == p ? buf : Arrays.copyOf(buf, p);
		}
	 
		private char[][] nm(int n, int m) {
			char[][] map = new char[n][];
			for (int i = 0; i < n; i++)
				map[i] = ns(m);
			return map;
		}
	 
		private int[] na(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = ni();
			return a;
		}
	 
		private int ni() {
			int num = 0, b;
			boolean minus = false;
			while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
				;
			if (b == '-') {
				minus = true;
				b = readByte();
			}
	 
			while (true) {
				if (b >= '0' && b <= '9') {
					num = num * 10 + (b - '0');
				} else {
					return minus ? -num : num;
				}
				b = readByte();
			}
		}
	 
		private long nl() {
			long num = 0;
			int b;
			boolean minus = false;
			while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
				;
			if (b == '-') {
				minus = true;
				b = readByte();
			}
	 
			while (true) {
				if (b >= '0' && b <= '9') {
					num = num * 10 + (b - '0');
				} else {
					return minus ? -num : num;
				}
				b = readByte();
			}
		}
}