408313: GYM103091 M Plants

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

M. Plantstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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

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

ExamplesInput
5 3 5 2
1 4 8 4 1
Output
7
Input
5 3 100 2
1 4 8 4 1
Output
18
Note

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.

加入题单

上一题 下一题 算法标签: