SAC '22 Code Challenge 1 P5 - That Wall

View as PDF

Points: 12
Time limit: 1.0s
Java 2.0s
Memory limit: 256M

Author:
Problem type

You are the urban designer for a city with piles of candy that have different heights, , and are tasked with building a wall to hide them.

You will be penalized for your inaccuracy in building a wall to hide each of these piles, .

Specifically, you will be fined , where is the height that you build the final wall for the pile of candy. (Showing the candy or hiding scenic scenery is equally bad.)

Each pillar of the wall has an initial height of .

Additionally, you can only change the height of a given wall up to times along its length (i.e., set the heights of all the pillars of the wall from to a height).

Find the minimum cost for this wall.

Input Specification

The first line will contain and , the number of piles of candy that need to be covered and the number of changes you can make.

The second line will contain space-separated integers, , the cost for each difference in height between the piles of candy and wall.

The third line will contain space-separated integers, , the optimal height for this pillar.

Output Specification

Output the minimum cost to be fined for building this wall.

Sample Input

5 1
1 10 3 5 2
1 10 4 3 2

Sample Output

70

Explanation for Sample Output

Note that there are multiple valid solutions yielding the minimum cost.

Here is one valid solution:

Spend the first and only move to set the height for all pillars from to , resulting in a total cost of .