은기는 음이 아닌 정수 n개로 이루어진 수열을 이용해 시간을 때우고 있다. 은기는 수열을 총 k+1개로 나누어야 하고, 각 부분은 비어있지 않아야 한다. 수열을 k+1개로 나누러면, 아래와 같은 과정을 k번 반복해야 한다.

1. 원소를 두 개 이상 가지고 있는 부분을 고른다. (가장 처음에는 수열 전체밖에 없다)
2. 임의의 두 원소 사이를 기준으로 수열을 두 부분으로 나눈다.

위의 과정을 할 때마다 얻게되는 점수는 새로 나누어진 각 부분에 들어있는 원소의 합을 곱한 것이다. 위의 과정을 k번 반복하면서 은기가 얻을 수 있는 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력 형식

첫째 줄에 두 정수 n과 k가 주어진다. (2 ≤ n ≤ 100,000, 1 ≤ k ≤ min(n-1, 200)) 둘째 줄에는 수열을 나타내는 음이 아닌 정수 n개 a₁, a₂, ..., a_n이 주어진다. (0 ≤ a_i ≤ 10⁴)

출력 형식

첫째 줄에 얻을 수 있는 가장 큰 점수를 출력한다. 둘째 줄에는 그러한 점수를 얻기 위해 몇 번째 원소 다음에 수열을 나누어야 하는지 순서대로 출력한다. 가능한 답이 여러개라면, 아무거나 출력한다.

예제 입력

7 3
4 1 3 4 0 2 3

예제 출력

108
1 3 5

힌트

아래와 같은 과정으로 수열을 나누면 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개의 부분 (4), (1, 3), (4, 0), (2, 3) 으로 나누어지게 되고, 은기가 얻은 점수는 52 + 36 + 20 = 108점이다.