수열 Batch 컴파일 명령

음수가 아닌 자연수 $n$개가 원소인 수열을 가지고 어떤 게임을 하려고 한다. 이 게임에서는 수열을 $k+1$개의 부분으로 나누어야 한다. 수열을 $k+1$개의 부분으로 나누기 위해서 다음의 과정을 $k$번 반복한다.

1. 두 개 이상의 자연수를 가진 부분을 선택한다. (처음에는 수열 전체가 하나의 부분이다.)
2. 선택된 부분의 연속한 두 원소 사이를 자르는 것으로 두 부분이 만들어진다. 이 과정을 한번 할 때 마다 점수를 얻는데, 그 점수는 만들어진 각 부분에 있는 수들을 합하여 얻는 두 수의 곱이다. 전체 과정에서 얻는 점수의 합을 최대로 하고 싶다.

입력

입력의 첫 번째 줄에는 자연수 두 개가 주어지는데 각각 $n$과 $k$이다. ($k+ 1 < n$) 두 번째 줄에는 입력수열이 $n$개의 음수가 아닌 자연수로 주어진다. 각 수는 0 이상 $10^4$ 이하이다.

출력

입력의 첫 줄에 얻을 수 있는 가장 큰 점수를 출력한다. 입력의 둘째 줄에는 $k$개의, 1 이상 $n-1$ 이하인 자연수를 출력하는데, 이들은 가장 큰 점수를 얻기 위해 수열을 자르는 방법을 (최초 수열에서의) 위치로 제시한 것이다. 위치는 수열을 자르는 곳 바로 앞에 있는 원소의 위치이다. 즉, 4번째와 5번째 수 사이를 잘랐다면 4를 출력하는 것이다. 최대의 점수를 얻는 방법이 여러 가지가 있다면 그 중 아무 것이나 하나를 출력하면 된다.

입출력 예

추가설명

입출력 예에서 108점을 얻는 방법은 아래와 같다.

• 처음에 전체 수열인 $(4, 1, 3, 4, 0, 2, 3)$이 있다. 이 수열을 첫 번째 원소 다음에서 잘라서 $52$점($= 4 \times (1+ 3 +4 + 0 +2 + 3)$)을 얻는다.
• 이제 $(4)$와 $(1, 3, 4, 0, 2, 3)$의 두 부분이 생기는데 이를 세 번째 원소 다음에서 잘라서 $36$점($= (1 +3) \times (4 + 0+ 2 +3)$)을 얻는다.
• 이제 $(4)$, $(1, 3)$, $(4, 0, 2, 3)$의 세 부분이 있는데 이를 다섯 번째 원소 다음에서 잘라서 $20$점($= (4 +0) \times (2 + 3)$)을 얻는다.

최종적으로 네 부분 $(4)$, $(1, 3)$, $(4, 0)$, $(2, 3)$이 남고, 얻는 점수는 $52 + 36 + 20 = 108$점이다.

채점

다음과 같은 여섯 개의 서브태스크로 채점이 이루어 진다.

서브태스크 1 (11점)

$1 \le k < n \le 10$

서브태스크 2 (11점)

$1 \le k < n \le 50$

서브태스크 3 (11점)

$1 \le k < n \le 200$

서브태스크 4 (17점)

$2 \le n \le 1000$, $1 \le k \le \min (n-1, 200)$

서브태스크 5 (21점)

$2 \le n \le 10000$, $1 \le k \le \min (n-1, 200)$

서브태스크 6 (29점)

$2 \le n \le 100000$, $1 \le k \le \min (n-1, 200)$