You are playing a game with a sequence of non-negative integers. In this game you have to split the sequence into
non-empty parts. To obtain
parts you repeat the following steps
times:
Choose any part with more than one element (initially you have only one part – the whole sequence).
Split it between any two elements to get two new non-empty parts.
Each time after these steps you gain the number of points which is equal to product of sums of elements of each new part. You want to maximize the total number of points you gain.
Input Specification
The first line of the input file contains two integers and
(
). The second line of input contains
non-negative integers
(
) – the sequence.
Output Specification
On the first line output the largest total number of points you can gain. On the second line output integers between
and
— 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.
Scoring
Your program will be tested on 6 sets of input instances as follows:
Subtask 1 (points: 11)
.
Subtask 2 (points: 11)
.
Subtask 3 (points: 11)
.
Subtask 4 (points: 17)
.
Subtask 5 (points: 21)
.
Subtask 6 (points: 29)
.
Sample Input
7 3
4 1 3 4 0 2 3
Sample Output
108
1 3 5
Note
In the first sample you can gain points by the following way:
- Initially you have the whole sequence
as one part. You will split the sequence after 1st element and gain
points.
- You have two parts
. You will split the sequence after 3rd element and gain
points.
- You have three parts
. You will split the sequence after 5th element and gain
points.
So, after the steps taken above you get four parts and gain
points.
Comments