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.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;

public class D {

	public static void main(String[] args) {
		
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		
		long[] vol = new long[n];
		
		for(int i = 0; i < n; i++) {
			int r = scanner.nextInt();
			int h = scanner.nextInt();
			vol[i] = (long) (Math.pow(r, 2) * h);
			
		}
		
		long[] sort = Arrays.copyOf(vol, n);
		Arrays.sort(sort);
		Map<Long, Integer> map = new HashMap<Long, Integer>();
		int count = 0;
		for(long e : sort) {
			if(!map.containsKey(e)) {
				map.put(e, count++);
			}
			
		}
		
//		for(Entry<Integer, Integer> e : map.entrySet()) {
//			System.out.println("K: " + e.getKey() + " V: " + e.getValue());
//			
//		}
		
		long[] zeroes = new long[n];
		SegmentTree tree = new SegmentTree(zeroes);
		
		for(int i = 0; i < n; i++) {
			long prev = (map.get(vol[i]) == 0) ? 0 : tree.RMaxQ(0, map.get(vol[i]) - 1);
			tree.update(map.get(vol[i]) , map.get(vol[i]) , prev + vol[i]);
			
		}
		
		System.out.println(Math.PI * tree.RMaxQ(0, n - 1));
		
		
		
	}
	
	public static class SegmentTree {

		private Node[] heap;
		private long[] array;
		private int size;

		/**
		 * Time-Complexity:  O(n*log(n))
		 *
		 * @param array the Initialization array
		 */
		public SegmentTree(long[] array) {
			this.array = Arrays.copyOf(array, array.length);
			//The max size of this array is about 2 * 2 ^ log2(n) + 1
			size = (int) (2 * Math.pow(2.0, Math.floor((Math.log((double) array.length) / Math.log(2.0)) + 1)));
			heap = new Node[size];
			build(1, 0, array.length);
		}


		public int size() {
			return array.length;
		}

		//Initialize the Nodes of the Segment tree
		private void build(int v, int from, int size) {
			heap[v] = new Node();
			heap[v].from = from;
			heap[v].to = from + size - 1;

			if (size == 1) {
				heap[v].sum = array[from];
				heap[v].min = array[from];
				heap[v].max = array[from];
			} else {
				//Build childs
				build(2 * v, from, size / 2);
				build(2 * v + 1, from + size / 2, size - size / 2);

				heap[v].sum = heap[2 * v].sum + heap[2 * v + 1].sum;
				//min = min of the children
				heap[v].min = Math.min(heap[2 * v].min, heap[2 * v + 1].min);
				heap[v].max = Math.max(heap[2 * v].max, heap[2 * v + 1].max);
				
			}
		}

		/**
		 * Range Sum Query
		 *
		 * Time-Complexity: O(log(n))
		 */
		public long RSQ(int from, int to) {
			return RSQ(1, from, to);
		}

		private long RSQ(int v, int from, int to) {
			Node n = heap[v];

			//If you did a range update that contained this node, you can infer the Sum without going down the tree
			if (n.pendingVal != null && contains(n.from, n.to, from, to)) {
				return (to - from + 1) * n.pendingVal;
			}

			if (contains(from, to, n.from, n.to)) {
				return heap[v].sum;
			}

			if (intersects(from, to, n.from, n.to)) {
				propagate(v);
				long leftSum = RSQ(2 * v, from, to);
				long rightSum = RSQ(2 * v + 1, from, to);

				return leftSum + rightSum;
			}

			return 0;
		}

		/**
		 * Range Min Query
		 * 
		 * Time-Complexity: O(log(n))
		 */
		public long RMinQ(int from, int to) {
			return RMinQ(1, from, to);
		}

		private long RMinQ(int v, int from, int to) {
			Node n = heap[v];


			//If you did a range update that contained this node, you can infer the Min value without going down the tree
			if (n.pendingVal != null && contains(n.from, n.to, from, to)) {
				return n.pendingVal;
			}

			if (contains(from, to, n.from, n.to)) {
				return heap[v].min;
			}

			if (intersects(from, to, n.from, n.to)) {
				propagate(v);
				long leftMin = RMinQ(2 * v, from, to);
				long rightMin = RMinQ(2 * v + 1, from, to);

				return Math.min(leftMin, rightMin);
			}

			return Integer.MAX_VALUE;
		}
		
		/**
		 * Range Max Query
		 * 
		 * Time-Complexity: O(log(n))
		 */
		public long RMaxQ(int from, int to) {
			return RMaxQ(1, from, to);
		}

		private long RMaxQ(int v, int from, int to) {
			Node n = heap[v];


			//If you did a range update that contained this node, you can infer the Min value without going down the tree
			if (n.pendingVal != null && contains(n.from, n.to, from, to)) {
				return n.pendingVal;
			}

			if (contains(from, to, n.from, n.to)) {
				return heap[v].max;
			}

			if (intersects(from, to, n.from, n.to)) {
				propagate(v);
				long leftMax = RMaxQ(2 * v, from, to);
				long rightMax = RMaxQ(2 * v + 1, from, to);

				return Math.max(leftMax, rightMax);
			}

			return 0;
		}

		/**
		 * Range Update Operation.
		 * With this operation you can update either one position or a range of positions with a given number.
		 * The update operations will update the less it can to update the whole range (Lazy Propagation).
		 * The values will be propagated lazily from top to bottom of the segment tree.
		 * This behavior is really useful for updates on portions of the array
		 * <p/>
		 * Time-Complexity: O(log(n))
		 *
		 * @param from
		 * @param to
		 * @param value
		 */
		public void update(int from, int to, long value) {
			update(1, from, to, value);
		}

		private void update(int v, int from, int to, long value) {

			//The Node of the heap tree represents a range of the array with bounds: [n.from, n.to]
			Node n = heap[v];

			/**
			 * If the updating-range contains the portion of the current Node  We lazily update it.
			 * This means We do NOT update each position of the vector, but update only some temporal
			 * values into the Node; such values into the Node will be propagated down to its children only when they need to.
			 */
			if (contains(from, to, n.from, n.to)) {
				change(n, value);
			}

			if (n.size() == 1) return;

			if (intersects(from, to, n.from, n.to)) {
				/**
				 * Before keeping going down to the tree We need to propagate the
				 * the values that have been temporally/lazily saved into this Node to its children
				 * So that when We visit them the values  are properly updated
				 */
				propagate(v);

				update(2 * v, from, to, value);
				update(2 * v + 1, from, to, value);

				n.sum = heap[2 * v].sum + heap[2 * v + 1].sum;
				n.min = Math.min(heap[2 * v].min, heap[2 * v + 1].min);
				n.max = Math.max(heap[2 * v].max, heap[2 * v + 1].max);
				
			}
		}

		//Propagate temporal values to children
		private void propagate(int v) {
			Node n = heap[v];

			if (n.pendingVal != null) {
				change(heap[2 * v], n.pendingVal);
				change(heap[2 * v + 1], n.pendingVal);
				n.pendingVal = null; //unset the pending propagation value
			}
		}

		//Save the temporal values that will be propagated lazily
		private void change(Node n, long value) {
			n.pendingVal = value;
			n.sum = n.size() * value;
			n.min = value;
			n.max = value;
			array[n.from] = value;

		}

		//Test if the range1 contains range2
		private boolean contains(int from1, int to1, int from2, int to2) {
			return from2 >= from1 && to2 <= to1;
		}

		//check inclusive intersection, test if range1[from1, to1] intersects range2[from2, to2]
		private boolean intersects(int from1, int to1, int from2, int to2) {
			return from1 <= from2 && to1 >= from2   //  (.[..)..] or (.[...]..)
					|| from1 >= from2 && from1 <= to2; // [.(..]..) or [..(..)..
		}

		//The Node class represents a partition range of the array.
		class Node {
			long sum;
			long min;
			long max;
			//Here We store the value that will be propagated lazily
			Long pendingVal = null;
			int from;
			int to;

			int size() {
				return to - from + 1;
			}

		}
		
		
	}
	

}