408313: GYM103091 M Plants

Stanford and Berkeley are having a plant growing contest. Luckily some of the Stanford team members remembered from Biology class that watering plants helps them grow. The strategy they want to employ in order to win, is to water all of their plants as quickly as possible.

The students have $$$N$$$ labelled plants arranged in a line. They have a few operations they can perform. They can either

1. Water a singular plant by hand. The $$$i^{th}$$$ plant takes $$$t_i$$$ seconds to water.
2. Water a subarray of $$$K$$$ plants with a sprinkler. The sprinkler takes $$$W$$$ seconds to operate.
3. Swap two adjacent plants, which takes $$$S$$$ seconds to do.

The students can water each plant multiple times, but cannot perform more than one operation at a time. Compute the minimum amount of time needed to water each plant at least once.

The first line will contain four space separated integers $$$N$$$ ($$$1 \leq N \leq 5000$$$), $$$K$$$ ($$$ 1 \leq K \leq N$$$), $$$W$$$ ($$$1 \leq W \leq 10^9$$$), and $$$S$$$ ($$$1 \leq S \leq 10^9$$$) which represent the number of plants, the size of the subarray the sprinkler can water a time, the time it takes to operate the sprinkler, and the time it takes to swap two plants.

The second line of input will contain $$$N$$$ integers $$$t_i$$$ ($$$1 \leq t_x \leq 10^9, 1 \leq i \leq N$$$) which represents the amount of time it takes to water each plant individually.

Output a single integer, the minimum amount of time needed to water all plants at least once.

5 3 5 2
1 4 8 4 1

7

5 3 100 2
1 4 8 4 1

18

Sample 1: In the first sample, we should use the sprinkler on the middle three elements, and manually water the two plants on the end. Sample 2: In the second sample, it's now just cheaper to water all of the plants by hand.