Namje Adventure

남제관 중앙에 싱크홀이 생겼다. 돌이 바닥에 닿을 때까지 걸린 시간으로 깊이를 잰 1333 패밀리는 호기심을 참지 못하고 탐험에 나선다. 주헌이가 취미로 쓰던 로프를 빌려 아래로 내려간다.

그림 1. 아래로 내려갈 수 있는 경우(좌)와 내려갈 수 없는 경우(우)

길이가 $L$인 로프를 쓰면 $1$부터 $L$까지 원하는 만큼 내려갈 수 있다. $i$만큼 내려가면 $x_i$만큼 에너지를 쓴다. 로프가 짧아서 매번 가장 위에 있는 사람만 움직인다. 이미 다른 사람이 있는 칸으로는 움직일 수 없다.

입구에서 잰 거리를 깊이라고 한다. 시작할 때 $N$명은 깊이 $1, 2, \dots, N$에 한 명씩 매달린다. 바닥에 닿으면 $N$명은 깊이 $D-N+1, D-N+2, \dots, D$에 한 명씩 있어야 한다. 누가 어디에 있는지는 따지지 않는다.

바닥까지 쓰는 에너지 합을 가장 작게 하려 한다. 그 최솟값을 구하라.

첫째 줄에 $N$, $D$, $L$이 주어진다. 둘째 줄에 $x_1, x_2, \dots, x_L$이 공백으로 구분되어 주어진다.

$N$, $D$, $L$과 $x_i$는 모두 정수이다. $1 \le N \le 3$이고 $5 \le L \le 12$이며 $2N \le D \le 10^{10}$이다. 모든 $i$에 대해 $1 \le x_i \le 1000$이다.

바닥에 도착할 때까지 쓰는 에너지의 최솟값을 한 줄에 출력한다.

그림 1은 이동 규칙을 보여준다. 목적지 칸이 비어 있으면 내려갈 수 있고 이미 누군가 있으면 내려갈 수 없다.

아래 그림은 도착 배치 두 가지를 보여준다. 왼쪽은 에너지를 가장 적게 쓰고 도착한 경우이고 오른쪽은 도착은 했지만 에너지를 더 쓴 경우이다.