n개의 자연수로 이루어진 수열이 있다. 

이 수열을 입력된 순서를 유지한 채로 k+1개의 부분수열로 나눈다. 

k+1개의 수열을 얻기 위하여 아래의 방법을 k번 반복한다.

1. 2개 이상의 원소를 가진 임의의 부분 수열을 선택한다. (처음 선택하는 수열은 주어진 수열 전체가 된다.)

2. 선택한 부분 수열에 있는 임의의 어느 두 원소 사이를 나누어 두 개의 그룹으로 나눈다.

위와 같은 단계를 거친 후 점수를 얻게 되는데 그 점수는 각 단계에서 나누어진 두 부분수열의 합을 구하여 곱한 것을 모두 합한 것이 된다. 

얻게 되는 점수의 최대값을 구하는 프로그램을 작성하시오.

첫 행에 두 정수 n(2 ≤ n ≤​ 100,000)과 k( 1≤​ k ≤​ min(n-1, 200))이 입력된다.

두 번째 행에 n개의 음이 아닌 정수 a_i(0 ≤​ a_i ≤​ 10,000)가 공백으로 구분하여 입력된다.

첫 행에 얻을 수 있는 최대 점수를 출력한다.

두 번째 행에 최대점수를 얻게 하는 원소의 위치를 작업한 순서대로 출력한다. 

답이 여러 가지가 나오는 경우 그 중 한 가지만 출력한다.

예제에서 얻을 수 있는 최대 점수는 108이다.

- 초기에 주어진 수열은 (4, 1, 3, 4, 0, 2, 3) 이다. 먼저 첫 번째 원소와 나머지 원소들로 나누어 4 × (1 + 3 + 4 + 0 + 2 + 3) = 52점을 얻는다. 

- 이제 (4), (1, 3, 4, 0, 2, 3) 로 두 그룹이 된다. 3번째 원소를 선택하여 두 번째 그룹으로부터 (1 + 3) × (4 + 0 + 2 + 3) = 36점을 얻는다. 

- 이제 (4), (1,3), (4, 0, 2, 3) 로 세 그룹이 된다. 5번째 원소를 선택하여 세 번째 그룹으로부터 (4 + 0) × (2 + 3) = 20 점을 얻는다. 

따라서 (4), (1,3), (4,0), (2, 3)로 네 그룹이 되며 52 + 36 + 20 = 108점을 얻게 된다.