CF629D Babaei and Birthday Cake

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.

N/A

N/A

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