// Arup Guha
// 3/23/2024
// Solution to Spring 2024 COP 3503 Program 6 Part A: Maximum k-Partition GCD Sum

import java.util.*;

public class gcdsum {

	public static void main(String[] args) {
	
		// Get basic input.
		Scanner stdin = new Scanner(System.in);
		int n = stdin.nextInt();
		int k = stdin.nextInt();
		
		// Read sequence.
		int[] seq = new int[n];
		for (int i=0; i<n; i++)	
			seq[i] = stdin.nextInt();
			
		// Set up DP arrays.
		long[][] dp = new long[k][n];
		int[][] start = new int[k][n];
		
		// First row is just regular gcds from beginning.
		dp[0][0] = seq[0];
		for (int i=1; i<n; i++) 
			dp[0][i] = gcd((int)dp[0][i-1], seq[i]);
		
		// i+1 is number of partitions.
		for (int i=1; i<k; i++) {
		
			// -1 means we can't do it.
			Arrays.fill(dp[i], -1);
			
			// Considering partitioning seq[0..j]
			for (int j=i; j<n; j++) {
			
				// This is taking this last term by itself as the last partition.
				int curgcd = seq[j];
				dp[i][j] = dp[i-1][j-1] + curgcd;
				start[i][j] = j;
				
				// Consider starting this segment at index z.
				for (int z=j-1; z>=i; z--) {
					curgcd = gcd(curgcd, seq[z]);
					long alt = curgcd + dp[i-1][z-1];
					if (alt > dp[i][j]) {
						dp[i][j] = alt;
						start[i][j] = z;
					}
				}
			}
		}

		// Max gcd sum.
		System.out.println(dp[k-1][n-1]);
		
		// Reconstruct series, backwards.
		ArrayList<Integer> splits = new ArrayList<Integer>();
		int curloc = n-1;
		for (int i=0; i<k; i++) {
			splits.add(start[k-i-1][curloc]);
			if (i == k-1) break;
			curloc = start[k-i-1][curloc]-1;
		}
		
		// Reverse it so we can output in sorted order.
		Collections.reverse(splits);
		for (int i=0; i<splits.size(); i++)
			System.out.print( (splits.get(i)+1)+" ");
		System.out.println();
	}
	
	// Usual GCD function...
	public static int gcd(int a, int b) {
		return b == 0 ? a : gcd(b, a%b);
	}
}