Railway service points
Challenging climate and geography conditions on Iberian peninsula forced the management of Iberian Speed Railway (RFI) company to consider building a certain number of service points along the newly completed railway line. The railway runs between the west terminal in Lisabon, Portugal and the east terminal in Barcelona, Spain. It consists of a single line without any branchings. The next step in current planning is to choose the locations of the service points.
One service point is located in each terminal. These two service points have already been built and are not to be modified or upgraded in the foreseable future.
The length of the whole railway is L kilometers and each of the planned service points will be located at an integer distance (measured in kilometers) from the west terminal, that is, it will be located at one of possible distances 1, 2, ..., L−1 km from Lisabon.
For each of L−1 possible locations the cost of building and running a service point at this location was calculated.
The costs may differ significantly because of terrain, climate, local infrastructure and various other reasons.
The number N of planned service points is fixed and these N points will divide the entire railway into N+1 sections of various lengths.
It is not enough just to build the service points, also, the track sections between any two adjacent service points have to be maintained by the company.
Thorough economical analysis revealed that the maintenance cost grows quadratically with respect to the length of maintained section.
Therefore, there is a known function
CU(z) = a * z2 + b * z,
where z is the length of the section in km, a, b are fixed constants and CU(z) is the cost of maintenance of the track section of length z.
The function CU(z) is the same for all possible sections allong the whole railway. It is assumed that the additional cost of dealing with local conditions is included in the cost of building and running nearby service points.
Two or more service points cannot be built within the same kilometer distance from the terminal.
The task
You are given the number of planned service points, the costs of building and running a service point at each possible location and
the function CU(z) describing the maintenance cost of a railway track section of length z.
The task is to minimize the total cost of building all service points and maintaining the track sections between the service points.
Input
The input consists of three text lines. The first line contains two values L and N separated by space. L represents the length of the railway in kilometers, N represents the number of planned service points.
The second line contains parameters a and b of function CU(z) defined in the text above. The parameters are non-negative integers separated by space.
The third line contains a sequence of integers s1, s2, ..., sL−1, all separated by spaces. The value sk represents the cost of building and running a service point on the railway at k-th kilometer from the west terminal.
All relevant values sk, CU(z) are expressed in the same monetary units.
It holds 1 ≤ N < L ≤ 1000, 0 ≤ a, b, sk ≤ 1000.
Output
The output contains one text line with one integer representing the minimum total cost of building all planned service points and maintaining the track sections between the service points.
Example 1
Input4 1 2 3 5 22 13Output
37Service point is built at kilometer 1.
Example 2
Input6 1 1 1 40 20 1 20 40Output
25Service point is built at kilometer 3.
Example 3
Input10 2 5 0 1 20 26 20 2 23 24 23 3Output
212Service points are built at kilometer 2 and at kilometer 5.
Public data
The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set