뜨끈한 돼지국밥

"국밥 먹을바엔 뜨끈-하고 든든-한 돼지국밥 먹고 말지"

평소 돼지국밥에 대한 애정이 남다른 성우는 국밥의 인기가 치솟고 있는 시대 흐름에 발맞추어 돼지국밥 체인점으로 사업을 시작해보려고 한다. 전국적으로 사업을 넓히기 이전에 성우는 자신이 살고 있는 마을에서 먼저 사업을 시작하려고 한다.

성우가 살고 있는 동네는 일직선의 해안도로를 따라 길게 형성되어 있다. 해안도로를 기준으로 한쪽에는 바다가 있고, 다른 한쪽에는 사람들의 거주지가 있다. 사람들의 거주지는 일정한 간격으로 길가를 따라 일렬로 있고, 1번부터 50,000번까지의 자연수를 주소로 사용하고 있다. 임의의 두 거주지 사이의 거리는 두 거주지의 주소값의 차이와 같다.

성우는 사업을 시작하기 전 초기 비용이 얼마나 필요할지 계산했다. 그 결과 사업에 필요한 초기 비용은 체인점 건설비용과 총 배달비의 합과 같다는 결론을 내렸다. 배달비가 얼마 나올지 계산을 정확하게 하기 위해 성우는 마을 사람들을 대상으로 돼지국밥을 시켜 먹을 의향이 있는지 설문조사를 했고, 배달시킬 사람들의 주소를 알게 되었다. 체인점의 수를 $K$, 체인점 하나를 짓는 비용을 $M$, 기름값을 $C$, 배달시킬 사람들의 수를 $N$, 배달시킬 사람들의 주소 정보를 $L$로 설정하여 식으로 표현하면 아래와 같다.

$f(x) = \text{주소가 } x \text{인 지점에서 가장 가까운 체인점까지의 거리}$

체인점은 1번부터 50000번 사이의 모든 주소에 지을 수 있고, 성우는 지어야 하는 체인점의 수가 주어지면, 그때의 초기비용이 최소가 되도록 체인점의 위치를 배치하는 능력이 있다. 그렇기 때문에, 성우는 초기비용을 최소로 만드는 체인점의 수를 알려고 한다. 성우를 도와 초기 비용의 최솟값과 그때 지어야 하는 체인점의 수를 출력하자.

단, 초기 비용이 같은 경우 지어야 하는 체인점의 수가 더 적은 것을 선택한다.

첫째 줄에 배달시켜 먹을 사람들의 수 $N$이 정수로 주어진다. (1 ≤ $N$ ≤ 5,000)

둘째 줄에 배달시켜 먹을 사람들의 주소들이 빈 칸을 기준으로 구분되어 주어진다.

셋째 줄에는 기름값 $C$와 체인점을 하나 짓는데 드는 금액 $M$이 자연수로 주어진다. (1 ≤ $C$ ≤ 1,000, 1 ≤ $M$ ≤ 1,000,000)

초기 비용의 최솟값과, 그때 지어야 하는 체인점의 수를 출력하라.