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 r_{i} and h_{i} (1 ≤ r_{i}, h_{i} ≤ 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 $\frac{|a - b|}{\operatorname{max}(1, b)} \leq 10^{-6}$.


-----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.

Difficulty: interview

Starter code:

Solutions:
import math
from functools import reduce
class SegmentTree():
    def __init__(self, L, function = lambda x,y: x+y):
        self.function = function
        N = self.size = len(L)
        M = 1 << N.bit_length()
        self.margin = 2*M - N
        self.L = [None for i in range(self.margin)] + L
        for i in range(M-1, 0, -1):
            x, y = self.L[i<<1], self.L[i<<1|1]
            self.L[i] = None if x is None or y is None else function(x, y)
    def modify(self, pos, value):
        p = pos + self.margin
        self.L[p] = value 
        while p > 1:
            x, y = self.L[p], self.L[p^1]
            if p&1: x, y = y, x
            self.L[p>>1] = None if x is None or y is None else self.function(x, y)
            p>>=1
    def query(self, left, right):
        l, r = left + self.margin, right + self.margin
        stack = []
        void = True
        while l < r:
            if l&1:
                if void:
                    result = self.L[l]
                    void = False
                else:
                    result = self.function(result, self.L[l])
                l+=1
            if r&1:
                r-=1
                stack.append(self.L[r])
            l>>=1
            r>>=1
        init = stack.pop() if void else result
        return reduce(self.function, reversed(stack), init)

n = int(input())
pies, index, first_equal = [0]*n, [0]*n, [0]*n
for i in range(n):
    r, h = [int(x) for x in input().split()]
    pies[i] = r*r*h
s_pies = list(sorted(enumerate(pies), key = lambda p: p[1]))
for i in range(n): index[s_pies[i][0]] = i
for i in range(1, n):
    first_equal[s_pies[i][0]] = i if s_pies[i][1] != s_pies[i-1][1] else first_equal[s_pies[i-1][0]]
towers = SegmentTree([0]*(n+1), max)
for j, pie in enumerate(pies):
    i, k = index[j], first_equal[j]
    q = towers.query(0, k+1)
    towers.modify(i+1, q + pie)
print(math.pi * towers.query(0, n+1))


from math import *
from bisect import *

def update(bit, size, idx, amount):
    while idx <= size:
        if bit[idx] < amount:
            bit[idx] = amount
        idx += idx & -idx

def read(bit, idx):
    rst = 0
    while idx >= 1:
        if bit[idx] > rst:
            rst = bit[idx]
        idx -= idx & -idx
    return rst

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
arr = [r*r*h for r, h in arr]

arr2 = sorted(list(set(arr)))
n2 = len(arr2)
bit = [0] * (n2 + 1)

for v in arr:
    idx = bisect(arr2, v)
    update(bit, n2, idx, read(bit, idx-1) + v)

print(pi*max(bit))


from math import *
from bisect import *

def update(bit, size, idx, amount):
    while idx <= size:
        if bit[idx] < amount:
            bit[idx] = amount
        idx += idx & -idx

def read(bit, idx):
    rst = 0
    while idx >= 1:
        if bit[idx] > rst:
            rst = bit[idx]
        idx -= idx & -idx
    return rst

n = int(input())
arr = [map(int, input().split()) for _ in range(n)]
arr = [pi*(r*r*h) for r, h in arr]

arr2 = sorted(list(set(arr)))
n2 = len(arr2)
bit = [0.0] * (n2 + 1)

for v in arr:
    idx = bisect(arr2, v)
    update(bit, n2, idx, read(bit, idx-1) + v)

print(max(bit))

from sys import *
t = list(map(int, stdin.read().split()))
p = [t[i + 1] * t[i] ** 2 for i in range(1, len(t), 2)]
k = {v: j for j, v in enumerate(sorted(set(p)))}
d = [0] * (len(k) + 1)
for v in p: 
    j = k[v]
    i = j + 1
    q = 0
    while j > 0:
        q = max(d[j], q)
        j -= j & -j
    q += v
    while i < len(d):
        d[i] = max(d[i], q)
        i += i & -i
print(max(d) * 3.14159265)

from sys import *
t = list(map(int, stdin.read().split()))
p = [t[i + 1] * t[i] ** 2 for i in range(1, len(t), 2)]
k = {v: j for j, v in enumerate(sorted(set(p)))}
d = [0] * (len(k) + 1)
for v in p: 
    j = k[v]
    i = j + 1
    q = 0
    while j > 0:
        q = max(d[j], q)
        j -= j & -j
    q += v
    while i < len(d):
        d[i] = max(d[i], q)
        i += i & -i
print(max(d) * 3.14159265)


from sys import *
t = list(map(int, stdin.read().split()))
p = [t[i + 1] * t[i] ** 2 for i in range(1, len(t), 2)]
k = {v: j for j, v in enumerate(sorted(set(p)))}
d = [0] * (len(k) + 1)
for v in p: 
    j = k[v]
    i = j + 1
    q = 0
    while j > 0:
        q = max(d[j], q)
        j -= j & -j
    q += v
    while i < len(d):
        d[i] = max(d[i], q)
        i += i & -i
print(max(d) * 3.14159265)


from math import pi
n = int(input())
secuencia = [None] * n
maximo_to = -1
for num in range(n):
    r, h = (int(x) for x in input().strip().split())
    secuencia[num] = [r * r * h, num + 1]
secuencia.reverse()
secuencia.sort(key=lambda x: x[0])
actual = 0
bit = [0] * (n + 1)

def max_x(x, l):
    suma = 0
    while x != 0:
        suma = max(suma, l[x])
        x -= (x & -x)
    return suma

def update_x(x, l, max_n, val):
    while x <= max_n:
        if val > l[x]:
            l[x] = val
        else:
            return
        x += (x & -x)
for e in range(n):
    maximo = secuencia[e][0] + max_x(secuencia[e][1] - 1, bit)
    update_x(secuencia[e][1], bit, n, maximo)
    if maximo > maximo_to:
        maximo_to = maximo
print(maximo_to * pi)