| Codeforces Round 343 (Div. 2) |
|---|
| Закончено |
Как вы знаете, на дне рождения обязательно должен быть пирог! В этот раз Бабай решил приготовить особенный пирог.
Простой пирог можно представить как цилиндр некоторого радиуса и некоторой высоты. Объём простого пирога равен объёму соответствующего цилиндра. У Бабая есь n простых пирогов, и он хочет собрать особенный пирог, поставив некоторые из них друг на друга.
Однако есть дополнительные кулинарные ограничения. Пироги пронумерованы в некотором порядке, таком что пирог с номером i может быть поставлен только на стол или на пирог с номером j, где j < i. Более того, чтобы поразить своих друзей, Бабай будет ставить пирог i на пирог j, только если объём пирога i строго больше объёма пирога j.
Бабай хочет собрать пирог максимального суммарного объёма, помогите ему в этом.
В первой строке входных данных записано единственно число n (1 ≤ n ≤ 100 000) — количество простых пирогов в распоряжении Бабая.
В i-й из последующих n строк записаны два целых числа ri и hi (1 ≤ ri, hi ≤ 10 000) — радиус и высота i-го просто пирога соответственно.
Выведите максимальный объём пирога, который может собрать Бабай. Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не будет превосходить 10 - 6.
А именно: пусть ваш ответ равен a, а ответ жюри — b. Проверяющая программа будет считать ваш ответ правильным, если 
.
2
100 30
40 10
942477.796077000
4
1 1
9 7
1 4
10 7
3983.539484752
В первом примере оптимальным ответом будет просто выбрать пирог с номером 1.
Во втором примере максимальный объём специального пирога можно получить выбрав простые пироги 1, 2 и 4.
