Nothing mortal arrives faster than these messengers.
- Herodotus, Histories, Book VIII, Chapter 98
You are a messenger who must deliver an order to a distant destination and return with a reply. Relay stations have been set up along the road so that you can keep traveling by changing horses.
There are relay stations along the road, numbered through in order. The distance between stations and is . You depart from station , travel to station , and then return to station along the same road. Your travel order is fixed as follows; no other moves are allowed.
The first line contains the number of stations .
The second line contains the segment distances , separated by spaces.
Print the minimum time needed for the round trip.
In the first example, ride the first horse from station to station , then return on the same horse. The round trip takes units of time.
Initially, each station has exactly two horses. Riding horse initially at station takes units of time per unit distance. Therefore, riding this horse over a distance of takes units of time.
For each segment, choose one horse currently at the departure station and ride it to the next station. The horse stays at the arrival station. You may also reuse a horse from the outward journey on the return journey.
To give the horses a rest, you may not ride the same horse on two consecutive segments. The only exception to this rule is when you turn back at station . At station , the horse also rests while the reply is prepared, so you may return on the horse you just rode.
The round-trip time is the sum of the times spent riding a horse along each segment of the journey. Given the horses initially at each station, find the minimum time needed for the round trip.
The -th of the next lines contains the times per unit distance of the two horses initially at station , and , separated by a space.
In the second example, you can travel as follows.
The total time is , and no faster round trip is possible.
