There is only one branch-line of Yekaterinburg subway. But what a branch-line! Each station is an architectural masterpiece. It is no wonder that all the guests of our city try to have time to observe our subway in detail. And, as usual, the tourists try to manage in the minimal possible time – they have much to see! In an effort to make Yekaterinburg more attractive the city administration decided to work out a program that would calculate the optimal, in respect to the time, route passing all the stations. Of course, the turn of speech “the city administration decided to work out a program” doesn’t represent the facts exactly – the administration decided and this is your team who is to work it out.
The subway contains one branch-line. The trains run here with a definite interval that is evaluated by the integer number of minutes, intervals between the stations are known as well (they are evaluated by the integer number of minutes, too). You may assume that train stops at each station are instant. A tourist leaves a train instantly and it takes one second to board a train. A tourist needs 58 seconds to admire at a station. At the end of the sight seeing a tourist is to return to the starting station of his trip. He has already seen the station in the very beginning and so you are not to add the time of seeing it to the total trip time. A tourist may start his observation any time he likes, so the total trip time is to be counted out from the moment that he enters the train at the departure station.
The first line contains the number of stations N (1 ≤ N ≤ 16). The stations are numbered from 1 to N. The second line consists of N − 1 nonnegative number of minutes that doesn’t exceed 105—the time that a train runs from the first station to the second. From the second to the third, and so on (surely a train runs from the i-th to (i+1)st station and from the (i+1)st to the ith the same time). The third line contains the number of station that is the initial point of the trip. The fourth consists of three numbers: an interval between the trains, the departure time of the first train from the first station and the departure time of the first train from the N-th station;. all the numbers are nonnegative integers and measure minutes. The interval between the trains is nonzero and doesn’t exceed 105, and the departure time from the terminal stations doesn’t exceed the interval.
should contain the duration of the shortest possible observation of all the stations in minutes.
4 0 1
Problem Author: Leonid Volkov (prepared Leonid Volkov and Alexander Somov)
Problem Source: Ural State University championship, October 25, 2003