Warm Pork Gukbap

Time limit1sMemory limit256 MB

Summary

Place any number of stores on a line of positions 1 to 50000, each store costs M, each delivery costs C times distance to nearest store; find the minimum total cost and the smallest number of stores achieving it.

Level: Hard8 of 10
Topics: Dynamic programming, Binary search, Sorting, Greedy
Solved: No attempts yet

Problem

"If I'm going to eat gukbap, I'd rather have a warm, hearty bowl of pork gukbap."

Seongwoo has always had a special love for pork gukbap, and with the dish growing more popular, he decides to start a pork gukbap chain business. Before expanding across the country, he wants to start in the village where he lives.

Seongwoo's neighborhood stretches out along a straight coastal road. On one side of the road is the sea, and on the other side are people's residences. The residences lie in a line along the road at regular intervals, and their addresses are the natural numbers from 1 to 50,000. The distance between any two residences equals the difference of their addresses.

Before starting the business, Seongwoo calculated how much initial cost he would need. He concluded that the initial cost equals the sum of the chain store construction cost and the total delivery cost. To calculate the delivery cost precisely, he surveyed the villagers about whether they would be willing to order pork gukbap, and learned the addresses of the people who want delivery. Let $K$ be the number of chain stores, $M$ the cost of building one chain store, $C$ the fuel price, $N$ the number of people to deliver to, and $L$ the address information of the people to deliver to. The formula is as follows.

$f(x) = \text{the distance from the point with address } x \text{ to the nearest chain store}$

A chain store can be built at any address between 1 and 50000, and given the number of chain stores to build, Seongwoo can place them so that the initial cost is minimized. Therefore, Seongwoo wants to know the number of chain stores that minimizes the initial cost. Help Seongwoo output the minimum initial cost and the number of chain stores to build at that time.

If two choices give the same initial cost, choose the one with fewer chain stores.

Input

The first line gives the number of people to deliver to, $N$ , as an integer. (1 ≤ $N$ ≤ 5,000)

The second line gives the addresses of the people to deliver to, separated by spaces.

The third line gives the fuel price $C$ and the cost $M$ of building one chain store as natural numbers. (1 ≤ $C$ ≤ 1,000, 1 ≤ $M$ ≤ 1,000,000)

Output

Output the minimum initial cost and the number of chain stores to build at that time.

Examples2

Example 1
Input
```
7
40 30 50 30 60 60 70
2 100
```
Expected output
```
260 2
```
Example 2
Input
```
7
40 30 50 30 60 60 70
2 150
```
Expected output
```
330 1
```