如你所知,每个生日聚会都有蛋糕!这次,巴巴伊要准备非常特别的生日派对蛋糕。
简单的蛋糕是一个具有一定半径和高度的圆柱体。简单蛋糕的体积等于相应圆柱体的体积。 Babaei 有 n 个简单的蛋糕,他将制作一个特殊的蛋糕,将一些圆柱体相互叠放。
但是,还有一些额外的烹饪限制。蛋糕的编号方式使得编号 i 的蛋糕只能放在桌子上或放在编号 j 的蛋糕上,其中 j < i。而且,为了给朋友留下深刻的印象,只有当蛋糕i的体积严格大于蛋糕j的体积时,Babaei才会将蛋糕i放在蛋糕j的上面。
Babaei想要准备一个总体积尽可能大的生日蛋糕。帮助他找到这个价值。
输入
输入的第一行包含一个整数 n (1 ≤ n ≤ 100 000) — Babaei 拥有的简单蛋糕的数量。
以下 n 行每行包含两个整数 ri 和 hi (1 ≤ ri, hi ≤ 10 000),给出第 i 个蛋糕的半径和高度。
输出
打印Babaei可以制作的蛋糕的最大体积。如果您的答案的绝对或相对误差不超过 10 - 6,则视为正确。
即:假设你的答案是a,陪审团的答案是b。如果 $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$,检查程序将认为您的答案正确。
示例
输入 #1
2 100 30 40 10
输出 #1
942477.796077000
输入 #2
4 1 1 9 7 1 4 10 7
输出 #2
3983.539484752
注意
在第一个示例中,最佳方法是选择蛋糕编号 1。
在第二个示例中,获得最大体积的方法是使用索引为 1、2 和 4 的蛋糕。