시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 48 12 6 27.273%

문제

총 L개의 칸이 일렬로 놓여져 있는 감옥이 있다. 각각의 칸은 1번부터 L번까지 번호가 매겨져 있다. i번 방에는 죄수가 한 명 들어있으며, 그 죄수의 탈옥력(탈옥을 할 수 있는 능력을 수치로 나타낸 것)은 Ci이다.

가장 이상적인 감시 방법은 각각의 칸을 감시하는 간수가 한 명씩 있는 것이고, 각각의 간수가 죄수를 한 명씩 감시하는 것이다. 하지만, 예산 문제 때문에 이 감옥에는 간수를 최대 G명 고용할 수 있다. 우리는 탈옥 위험도를 최소로 하게 간수를 고용하고 배치하려고 한다.

각각의 간수는 인접한 칸을 감시해야 한다. i번 칸의 탈옥 위험도 Ri는 탈옥력 Ci와 i번 칸을 감시하는 간수가 감시하고 있는 죄수의 수를 곱한 값이다. 감옥의 탈옥 위험도는 모든 칸의 탈옥 위험도 Ri를 더한 값이다.

L과 G, 그리고 각 칸에 들어있는 죄수의 탈옥력 Ci가 주어졌을 때, 탈옥 위험도의 최소값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 감옥의 크기 L(1 ≤ L ≤ 8000)과 간수의 수 G(1 ≤ G ≤ 800)이 주어진다.

둘째 줄에는 Ci가 주어진다. (1 ≤ Ci ≤ 109)

출력

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

예제 입력

6 3
11 11 11 24 26 100

예제 출력

299

힌트

한 간수가 1, 2, 3번 방을, 다른 간수가 4, 5번 방을, 다른 간수가 6번 방을 감시한다고 하면 탈옥 위험도가 최소가 된다.

1, 2, 3번 방을 감시하는 간수는 총 3명의 죄수를 감시하고 있기 때문에, 1, 2, 3번 방의 탈옥 위험도는 11*3이다.

4, 5번 방을 감시하는 간수는 총 2명의 죄수를 감시하고 있기 때문에, 4번 방의 탈옥 위험도는 24*2 = 48, 5번 방은 26*2 = 52이다.

6번 방의 탈옥 위험도는 100이 된다.

출처