Codeforces Round 189 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dp

geometry

*2100

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Kalila and Dimna in the Logging Industry

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputKalila and Dimna are two jackals living in a huge jungle. One day they decided to join a logging factory in order to make money.

The manager of logging factory wants them to go to the jungle and cut *n* trees with heights *a*_{1}, *a*_{2}, ..., *a*_{n}. They bought a chain saw from a shop. Each time they use the chain saw on the tree number *i*, they can decrease the height of this tree by one unit. Each time that Kalila and Dimna use the chain saw, they need to recharge it. Cost of charging depends on the id of the trees which have been cut completely (a tree is cut completely if its height equal to 0). If the maximum id of a tree which has been cut completely is *i* (the tree that have height *a*_{i} in the beginning), then the cost of charging the chain saw would be *b*_{i}. If no tree is cut completely, Kalila and Dimna cannot charge the chain saw. The chainsaw is charged in the beginning. We know that for each *i* < *j*, *a*_{i} < *a*_{j} and *b*_{i} > *b*_{j} and also *b*_{n} = 0 and *a*_{1} = 1. Kalila and Dimna want to cut all the trees completely, with minimum cost.

They want you to help them! Will you?

Input

The first line of input contains an integer *n* (1 ≤ *n* ≤ 10^{5}). The second line of input contains *n* integers *a*_{1}, *a*_{2}, ..., *a*_{n} (1 ≤ *a*_{i} ≤ 10^{9}). The third line of input contains *n* integers *b*_{1}, *b*_{2}, ..., *b*_{n} (0 ≤ *b*_{i} ≤ 10^{9}).

It's guaranteed that *a*_{1} = 1, *b*_{n} = 0, *a*_{1} < *a*_{2} < ... < *a*_{n} and *b*_{1} > *b*_{2} > ... > *b*_{n}.

Output

The only line of output must contain the minimum cost of cutting all the trees completely.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Examples

Input

5

1 2 3 4 5

5 4 3 2 0

Output

25

Input

6

1 2 3 10 20 30

6 5 4 3 2 0

Output

138

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/15/2024 10:07:56 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|