탈옥

칸 $L$개가 일렬로 놓인 감옥이 있다. 칸에는 1번부터 $L$번까지 번호가 붙어 있고, $i$번 칸에는 죄수가 한 명씩 들어 있다. $i$번 칸에 있는 죄수의 탈옥력은 $C_i$이며, 탈옥력은 죄수가 탈옥하는 능력을 수치로 나타낸 값이다.

가장 이상적인 감시 방법은 칸마다 간수를 한 명씩 두어서 간수 한 명이 죄수 한 명만 감시하는 것이다. 하지만 예산 때문에 이 감옥은 간수를 최대 $G$명까지만 고용할 수 있다. 탈옥 위험도가 가장 작아지도록 간수를 고용해서 배치하려고 한다.

간수 한 명은 번호가 연속한 칸만 감시하고, 모든 칸은 정확히 한 명의 간수가 감시한다. $i$번 칸의 탈옥 위험도 $R_i$는 탈옥력 $C_i$에 $i$번 칸을 맡은 간수가 감시하는 죄수 수를 곱한 값이다. 감옥의 탈옥 위험도는 모든 칸의 $R_i$를 더한 값이다.

$L$과 $G$, 각 칸에 있는 죄수의 탈옥력 $C_i$가 주어질 때 탈옥 위험도의 최솟값을 구하는 프로그램을 작성하시오.

첫째 줄에 감옥의 크기 $L$과 간수의 수 $G$가 공백으로 구분되어 주어진다. ($1 \le L \le 8000$, $1 \le G \le 800$)

둘째 줄에 $C_1, C_2, \dots, C_L$이 공백으로 구분되어 주어진다. ($1 \le C_i \le 10^9$)

첫째 줄에 탈옥 위험도의 최솟값을 출력한다.

첫 번째 예제에서 한 간수가 1, 2, 3번 칸을, 다른 간수가 4, 5번 칸을, 남은 간수가 6번 칸을 감시하면 탈옥 위험도가 최소가 된다.

1, 2, 3번 칸을 맡은 간수는 죄수 세 명을 감시하므로 세 칸의 탈옥 위험도는 각각 $11 \times 3 = 33$이다.

4, 5번 칸을 맡은 간수는 죄수 두 명을 감시하므로 4번 칸은 $24 \times 2 = 48$, 5번 칸은 $26 \times 2 = 52$이다.

6번 칸을 맡은 간수는 죄수 한 명만 감시하므로 6번 칸은 $100 \times 1 = 100$이다. 모두 더하면 $33 \times 3 + 48 + 52 + 100 = 299$이다.