You are playing a game with a sequence of n non-negative integers. In this game you have to split the sequence into k + 1 non-empty parts. To obtain k + 1 parts you repeat the following steps k times:

1. Choose any part with more than one element (initially you have only one part ? the whole sequence).
2. Split it between any two elements to get two new non-empty parts.

Note

• Initially you have the whole sequence (4, 1, 3, 4, 0, 2, 3) as one part. You will split the sequence after 1st element and gain 4 × (1 + 3 + 4 + 0 + 2 + 3) = 52 points.
• You have two parts (4), (1, 3, 4, 0, 2, 3). You will split the sequence after 3rd element and gain (1 + 3) × (4 + 0 + 2 + 3) = 36 points.
• You have three parts (4), (1,3), (4, 0, 2, 3). You will split the sequence after 5th element and gain (4 + 0) × (2 + 3) = 20 points.

입력

• The first line of the input file contains two integers n and k (k + 1 ≤ n).
• The second line of input contains n non-negative integers a1, a2, . . . , an (0 ≤ ai ≤ 10^4) - the sequence.

출력

• On the first line output the largest total number of points you can gain.
• On the second line output k integers between 1 and n - 1 - the positions of elements after which you have to split the sequence to gain the largest total number of points. If there are more than one way to gain the largest number of points output any one of them.

입출력 예

입력

7 3

출력

108

입력

4 1 3 4 0 2 3

출력

1 3 5

출처:apio2014