Cakes
Limits: 2 sec., 256 MiB
This statement was translated automatically from Ukrainian.
Our heroes came skiing. Before such an activity, you need to eat and gain strength. Marichka decided to make a cake.
To do this, she baked \(n\) cake layers. Zenyk knows the radius \(r_i\) and the volume \(v_i\) of each cake layer. In order to make a cake in the shape of a mountain, Marichka places the cake layers one on top of the other in such a way that the radius of the layer on top is strictly smaller than the radius of the layer below it.
Zenyk wants the largest possible cake so that he has enough energy for skiing for a long time.
Help Zenyk find the maximum volume of the cake that Marichka can make.
Input
The first line contains an integer \(n\) — the number of cake layers.
The second line contains \(n\) integers \(r_i\) — the radius of the \(i\)-th cake layer.
The third line contains \(n\) integers \(v_i\) — the volume of the \(i\)-th cake layer.
Output
Output an integer — the maximum volume of the cake.
Constraints
\(1 \le n \le 2 \cdot 10^5\),
\(1 \le r_i, v_i \le 10^9\).
10 points: \(n \le 5 \cdot 10^3\);
15 points: without additional constraints.
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 3 1 4 7 10 15 22 | 47 |
| Input (stdin) | Output (stdout) |
|---|---|
| 2 4 4 4 7 | 7 |
Notes
In the first example, you can put all the cake layers one on top of the other.
In the second example, out of two cake layers of the same radius, we choose the larger one.
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|