Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3075
Ticket

Time Limit: 3 Seconds      Memory Limit: 32768 KB

ZJU ICPC team is planning a training course in an N-day 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 round-trip air tickets for all members in order to build a harmonious society. The price of air ticket in ith day is Pi. If we come to school at the ith day and go back home at jth day, we need to pay Pi + Pj.

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 P1, P2, ..., Pn (0 <= Pi <= 100000), indicating the price of air ticket from the first day to the Nth day.

Please process to the end-of-file.

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
Submit    Status