강 건너기

Nefario 박사가 연구실에서 오래 지내다가 여행을 떠난다. 가는 길에 강을 하나 건너야 한다. 다행히 강에는 건너편으로 이어지는 일직선 위에 돌 $N$개가 놓여 있어서 발판으로 쓸 수 있다. 강의 폭, 즉 건너야 하는 전체 거리는 $L$이다.

박사의 스쿠터는 공중에 뜨지만 멀리 뛰지는 못해서, 더 멀리 뛰려면 로켓 부스터를 만들어야 한다. 부스터 가격은 성능에 따라 달라진다. 거리 $R$까지 뛸 수 있는 부스터를 만드는 비용은 $R^2$이다. 부스터는 여러 번 쓸 수 있지만 한 번 뛸 때마다 $C$가 더 든다. 예를 들어 사거리 $10$짜리 부스터를 만들어 다섯 번 뛰면 전체 비용은 $10^2 + 5 \times C = 100 + 5C$이다.

출발점은 이쪽 강가인 거리 $0$이고 도착점은 건너편 강가인 거리 $L$이다. 한 번 뛸 때는 앞으로 $R$ 이하만큼 이동하며, 착지하는 곳은 돌이거나 건너편 강가여야 한다.

강의 폭 $L$, 점프 한 번에 드는 비용 $C$, 돌 $N$개의 위치가 주어진다. 강을 건너는 최소 비용 $M$과 그때의 점프 횟수 $J$, 부스터의 사거리 $R$을 구하라.

위 그림에서 박사는 폭이 $6$인 강을 건넌다. 돌은 거리 $1$, $2$, $3$, $5$에 있다. 사거리 $3$짜리 부스터를 만들면 두 번 뛰어서 강을 건널 수 있다.

$1 \le L \le 10^9$, $0 \le C \le 10^6$, $0 \le N < 1000$이다. 돌의 위치는 $0$보다 크고 $L$보다 작은 정수다. 사거리 $R$은 양의 정수로 고른다. 값이 커지므로 64비트 정수를 써야 하고, 가능한 사거리를 모두 훑는 방법으로는 제한 시간 안에 풀 수 없다.

입력은 테스트 케이스 여러 개로 이루어진다. 각 테스트 케이스의 첫 줄에 정수 $L$, $C$, $N$이 주어진다. 차례대로 강의 폭, 점프 한 번에 드는 비용, 돌의 개수다. 다음 $N$개 줄에는 각각 돌 하나의 위치가 주어진다. 돌은 위치 순서대로 주어지지 않을 수 있다. 마지막 줄에는 $0$ 하나만 있고, 그 줄에서 입력이 끝난다.

각 테스트 케이스마다 강을 건너는 최소 비용을 한 줄에 다음 형식으로 출력한다.

Minimum cost M achieved with J jumps of range R

$M$은 최소 비용, $R$은 그 비용을 만드는 사거리, $J$는 사거리 $R$로 강을 건너는 데 필요한 최소 점프 횟수다. 최소 비용을 만드는 사거리가 여러 개면 그중 가장 작은 것을 $R$로 출력한다.