돌 분배

이노폴리스 스포츠 센터에는 놀라울 정도로 잘 갖춰진 첨단 사우나가 있다. 하지만 건설 과정에서 복잡한 기술이 사용되었기 때문에 사람들은 이 사우나를 제대로 관리하는 방법을 알지 못한다.

사우나에는 $n - 1$개의 연속한 칸이 있다. 인접한 두 칸 사이마다 난로가 하나씩 있다. 난로는 두 개 더 있는데, 하나는 첫 번째 칸에만 연결되어 있고 다른 하나는 마지막 칸에만 연결되어 있다. 따라서 난로는 모두 정확히 $n$개다.

$i$번째 칸의 부피는 $k_i$이다. 각 난로에는 0개부터 $v$개까지의 돌을 넣을 수 있다. $i$번째 난로에 들어 있는 돌의 수를 $p_i$라고 하면, $i$번째 칸은 $k_i \cdot p_i \cdot p_{i + 1}$만큼의 열을 받는다.

스포츠 센터에는 난로용 돌이 $s$개 있다. 스포츠 센터 관리팀은 다른 곳까지 데워지지 않도록 모든 칸이 받는 열의 합을 최소로 만들려고 한다. 하지만 돌을 사는 데 돈이 들었으므로 돌은 전부 사용해야 한다. 관리팀이 이 문제를 해결하도록 도와주자.

첫째 줄에는 세 정수 $n$, $s$, $v$가 주어진다. 각각 난로의 수, 돌의 수, 난로의 용량이다($2 \le n \le 1000$, $1 \le v \le 10^5$, $s \le n \cdot v$).

둘째 줄에는 $n - 1$개의 정수 $k_i$가 주어진다. $i$번째 칸의 부피이다($1 \le k_i \le 10^5$).

모든 칸이 받는 열의 합의 최솟값을 출력한다.

예제의 정답은 첫 번째와 마지막 난로에 돌을 네 개씩 넣고 두 번째 난로에 두 개를 넣으면 얻을 수 있다. 그러면 두 번째 칸을 제외한 모든 칸의 열은 0이고, 두 번째 칸의 열은 $8$이다.