You want to plan a training camp for your team in an N-days vacation (3 ≤ N ≤ 100000). The team must arrive at the camp before the first training day, and they may go home after the last training day. The training should be between P and Q days long, inclusive.

You decide to buy air tickets for all the team members. The price of air ticket in i^{th} day is A_{i}. If the team arrive at the i^{th} day and go back home at j^{th} day, you need to pay A_{i} + A_{j}. You notice that sometimes the cost will be lower if they arrive earlier or back home later (the team may have free days). For each free day, you should pay F for their extra lunch fee.

Find the minimal total cost, including air tickets and extra lunch fee.

Let’s simplify the problem by considering only the cases where P equals to Q, which means, the training days should always be Q days long. For each feasible choice of (i, j): arrive at i^{th} day and return at j^{th} day, we only have to concern with the air tickets (A_{i} + A_{j}) and the number of free days (free = j – i – Q – 1). When the training will be conducted does not matter as long as they’re somewhere between i^{th} and j^{th} day.

Let A_{i} be the day when the team arrives, A_{i+1..i+Q} are the training days, A_{i+1+Q} is the earliest day in which they can go home and A_{N} is the latest. We want to find j which minimize { A_{j} + free * F } and subject to i+1+Q ≤ j ≤ N. This can be done in O(1) by preprocessing table X_{1..N} in O(N). X_{k} means j which meets the above criteria for k = i+1+Q. Alternatively, we can modify X to keep only the total cost to return at j^{th} day as we don’t need the j value. This little modification may help you (at least me) in the implementation details.

To compute X_{k} we need to consider only A_{k} and X_{k+1}+F. This idea can be explained mathematically as follows:

X_{k}= min { A_{k}, A_{k+1}+F, A_{k}+2F, ..., A_{N}+(N-k)F } X_{k}= min { A_{k}, min{A_{k+1}+F, A_{k}+2F, ..., A_{N}+(N-k)F} } X_{k}= min { A_{k}, min{A_{k+1}, A_{k}+F, ..., A_{N}+(N-(k+1))F} + F } X_{k}= min { A_{k}, X_{k+1}+F }

A simple dynamic programming approach is sufficient to compute all X in O(N). The minimum cost if we arrive at i^{th} day is A_{i} + X_{i+1+Q}, which costs O(1). So, to find the minimum cost for all i will need only O(N) computation.

Now let’s back to the real problem where P could be less than Q.

Notice that any feasible j should fall into one of these ranges:

– between i+1+P and 1+Q, inclusive.

– between i+1+Q and N, inclusive.

The second range has been handled by table X, but how about the first range? The answer was quite simple, yet the implementation is more complex. To handle the first range, we just need to find the lowest A_{j} in all i+1+P ≤ j ≤ 1+Q. Why? The reason is obviously we don’t want a “must-pay” free day while we can have a “free” training days. So, force the students to train (no free day).

To find the minimum element in a certain range, there are several data structures such as segment-tree or range-minimum-query. Although, we can also manipulate the usage of STL’s priority_queue to perform such task (note that the range we want to check slides from left to right with a static length) .

The final answer can be found by chosing j (return day) with the minimum cost between first range and second range for each chosen i (arrival day).