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.io.*;
import java.util.*;
import java.math.*;

public class Main implements Runnable {
    public InputReader in;
    public PrintWriter out;

    public void solve() throws Exception {
        // solution goes here
        int N = in.nextInt();
        long[] volumes = new long[N];
        for (int i = 0; i < N; i++) {
            volumes[i] = volume(in.nextInt(), in.nextInt());
        }

        out.println(StrictMath.PI * maxSumIncreasingSequence(volumes));
    }

    private long maxSumIncreasingSequence(long[] array) {

        HashMap<Long, Integer> map = ranks(array);

        SegmentTree msis = new SegmentTree(new long[array.length]);

        for (int i = 0; i < array.length; i++) {
            Integer idx = map.get(array[i]);
            long cur = msis.rangeQuery(0, idx - 1) + array[i];
            msis.update_point(idx, cur);
        }

        return msis.rangeQuery(0, array.length);
    }

    private HashMap<Long, Integer> ranks(long[] array) {
        HashMap<Long, Integer> map = new HashMap<>(array.length << 1);
        long[] sorted = new long[array.length];
        System.arraycopy(array, 0, sorted, 0, array.length);
        Arrays.sort(sorted);
        for (int i = 0; i < array.length; i++)
            map.put(sorted[i], i);

        return map;
    }

    // without PI
    private long volume(long radius, long height) {
        return radius * radius * height;
    }

    static class SegmentTree {

        private long calculatingFunction(long p1, long p2) {
            return max(p1, p2);
        }

        private long[] segmentArray, originalArray;
        private int n;

        private int left(int p) { // same as binary heap operations
            return p << 1;
        }

        private int right(int p) {
            return (p << 1) + 1;
        }

        private int parent(int p) {
            return p >> 1;
        }
        private void buildDown(int p, int L, int R) {
            if (L == R)          // as L == R, either one is fine
                segmentArray[p] = originalArray[L];       // store the value
            else {              // recursively compute the values
                buildDown(left(p), L, (L + R) / 2);
                buildDown(right(p), (L + R) / 2 + 1, R);
                long p1 = segmentArray[left(p)], p2 = segmentArray[right(p)];

                segmentArray[p] = calculatingFunction(p1, p2);
            }
        }

        private long rangeQuery(int p, int L, int R, int low, int high) {          // O(log n)
            if (low > R || high < L) return 0;            // current segment outside query range
            if (L >= low && R <= high) return segmentArray[p];       // inside query range

            // compute the min position in the left and right part of the interval
            long p1 = rangeQuery(left(p), L, (L + R) / 2, low, high);
            long p2 = rangeQuery(right(p), (L + R) / 2 + 1, R, low, high);

            return calculatingFunction(p1, p2);   // as as in build routine
        }

        private int getSegmentTreeIndexOf(int idx) {
            int low = 0;
            int high = n - 1;

            int start = 1;
            int mid;
            while (high > low) {
                mid = (low + high) >> 1;
                if (idx > mid) {
                    low = mid + 1;
                    start = right(start);
                } else {
                    high = mid;
                    start = left(start);
                }
            }
            return start;
        }

        // Update point and propagate changes upwards
        public void update_point(int idx, long new_value) {

            int treeIndex = getSegmentTreeIndexOf(idx);

            // Don't forget to implements equals and hashcode
            if (segmentArray[treeIndex] == new_value)
                return;

            originalArray[idx] = new_value;
            segmentArray[treeIndex] = new_value;
            treeIndex = parent(treeIndex);

            while(treeIndex > 0) {
                new_value = calculatingFunction(segmentArray[left(treeIndex)], segmentArray[right(treeIndex)]);
                if (segmentArray[treeIndex] == new_value)
                    break;
                segmentArray[treeIndex] = new_value;
                treeIndex = parent(treeIndex);
            }
        }

        //  Increment elements within range [i, j] with value value
        void update_tree(int i, int j, int value) {
            update_tree(1, 0, originalArray.length - 1, i, j, value);
        }

        void update_tree(int node, int low, int high, int i, int j, int value) {

            if(low > high || low > j || high < i) // Current segment is not within range [i, j]
                return;

            if(low == high) { // Leaf node
                segmentArray[node] = value;
                return;
            }

            update_tree(left(node), low, (low+high)/2, i, j, value); // Updating left child
            update_tree(right(node), 1+(low+high)/2, high, i, j, value); // Updating right child

            segmentArray[node] = calculatingFunction(segmentArray[left(node)], segmentArray[right(node)]); // Update root
        }

        public SegmentTree(long[] array) {
            originalArray = array;
            n = originalArray.length;                               // copy content for local usage
            segmentArray = new long[4 * n];
            buildDown(1, 0, n - 1);                         // recursive build
        }

        // 0-index based
        public long rangeQuery(int i, int j) {  // overloading
            return rangeQuery(1, 0, n - 1, i, j);
        }

    }

    public void run() {
        try {
            in = new InputReader(System.in);
            out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
            Locale.setDefault(Locale.US);
            int tests = 1;
            while (tests-- > 0) {
                solve();
            }
            out.close();
        } catch (Throwable e) {
            e.printStackTrace();
            System.exit(7);
        }
    }

    static int abs(int x) {
        return x < 0 ? -x : x;
    }

    static int max(int a, int b) {
        return a > b ? a : b;
    }

    static int min(int a, int b) {
        return a < b ? a : b;
    }

    static long abs(long x) {
        return x < 0 ? -x : x;
    }

    static long max(long a, long b) {
        return a > b ? a : b;
    }

    static long min(long a, long b) {
        return a < b ? a : b;
    }

    private void swap(int[] array, int a, int b) {
        if (a != b) {
            array[a] = array[a] ^ array[b];
            array[b] = array[a] ^ array[b];
            array[a] = array[a] ^ array[b];
        }
    }

    private void swap(long[] array, int a, int b) {
        if (a != b) {
            array[a] = array[a] ^ array[b];
            array[b] = array[a] ^ array[b];
            array[a] = array[a] ^ array[b];
        }
    }

    private void swap(Object[] array, int a, int b) {
        Object temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }

    private void swap(char[] array, int a, int b) {
        char temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }

    public static void main(String args[]) {
        new Thread(null, new Main(), "Main", 1 << 28).start();
    }

    static boolean OJ = System.getProperty("ONLINE_JUDGE") != null;

    public void console(Object... objects) {
        if (!OJ) {
            out.println(Arrays.deepToString(objects));
            out.flush();
        }
    }

    @SuppressWarnings({"Duplicates", "unused"})
    static class InputReader {

        private InputStream stream;
        private byte[] buf = new byte[2048];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;

        public InputReader() {
            this.stream = System.in;
        }

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public InputReader(SpaceCharFilter filter) {
            this.stream = System.in;
            this.filter = filter;
        }

        public InputReader(InputStream stream, SpaceCharFilter filter) {
            this.stream = stream;
            this.filter = filter;
        }

        public int read() {
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public char nextChar() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            return (char) c;
        }

        public int nextDigit() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            return c - '0';
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            boolean negative = false;
            if (c == '-') {
                negative = true;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return negative ? -res : res;
        }

        public int[] nextInts(int N) {
            int[] nums = new int[N];
            for (int i = 0; i < N; i++)
                nums[i] = nextInt();
            return nums;
        }

        public long[] nextLongs(int N) {
            long[] nums = new long[N];
            for (int i = 0; i < N; i++)
                nums[i] = nextLong();
            return nums;
        }

        public int nextUnsignedInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int res = 0;
            do {
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res;
        }

        public final long nextLong() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            boolean negative = false;
            if (c == '-') {
                negative = true;
                c = read();
            }
            long res = 0;
            do {
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return negative ? -res : res;
        }

        public final long nextUnsignedLong() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            long res = 0;
            do {
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res;
        }

        public double nextDouble() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            long sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1 || c == '.'));

            if (c != '.') {
                return res * sgn;
            }
            c = read();

            long aft = 0;
            int len = 1;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                aft *= 10;
                len *= 10;
                aft += c - '0';
                c = read();
            } while (!isSpaceChar(c));

            return res * sgn + aft / (1.0 * len);
        }

        public String nextLine() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndChar(c));
            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public boolean isEndChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public String next() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public char[] nextChars() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));

            char[] chars = new char[res.length()];
            res.getChars(0, chars.length, chars, 0);
            return chars;
        }

        public int[][] nextIntMatrix(int rows, int cols) {
            int[][] matrix = new int[rows][cols];
            for (int i = 0; i < rows; i++)
                for (int j = 0; j < cols; j++)
                    matrix[i][j] = nextInt();
            return matrix;
        }

        public long[][] nextLongMatrix(int rows, int cols) {
            long[][] matrix = new long[rows][cols];
            for (int i = 0; i < rows; i++)
                for (int j = 0; j < cols; j++)
                    matrix[i][j] = nextLong();
            return matrix;
        }

        public char[][] nextCharMap(int rows, int cols) {
            char[][] matrix = new char[rows][cols];
            for (int i = 0; i < rows; i++)
                for (int j = 0; j < cols; j++)
                    matrix[i][j] = nextChar();
            return matrix;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }
}