
73  ZOJ Monthly, December 2008  C
ZJU ICPC team is planning a training course in an Nday vacation. Since the training is arranged in a long vacation, all team members should come to school before the beginning of training, and go back home after the end of the training. The training should be neither too long nor too short. So the coaches decide that the training should not be less than P days, and it should be no more than Q days. As a special offer, the head of the team decides to buy roundtrip air tickets for all members in order to build a harmonious society. The price of air ticket in i^{th} day is P_{i}. If we come to school at the i^{th} day and go back home at j^{th} day, we need to pay P_{i} + P_{j}. The head of the team wants to minimize the cost. He finds that sometimes the cost will be lower if we come to school earlier or back home later. As you may know, however, because the team will offer free lunch for members, more lunch fee is needed. The lunch fee is F per day. Now you task is to find the minimal cost, including the air ticket price and the extra lunch fee. Input The input contains multiple test cases, separated with a blank line. Each case begins with a line containing four integers N (3 <= N <= 100000), P, Q (0 < P <= Q < N  2), F (0 <= F <= 100000). The next line has N integers P_{1}, P_{2}, ..., P_{n} (0 <= P_{i} <= 100000), indicating the price of air ticket from the first day to the N^{th} day. Please process to the endoffile. Output For each case please output the minimal cost in integer. One test case per line. Sample Input 6 2 3 1 1 2 3 4 5 6 6 2 3 1 1 100 100 100 100 1 Sample Output 5 3 Author: LI, Cheng Source: ZOJ Monthly, December 2008 