// Arup Guha
// 6/26/2012
// Solution to 2008 Southeast Regional Problem: Lawrence of Arabia

import java.util.*;

public class c {

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);

		int N = stdin.nextInt();
		int M = stdin.nextInt();

		while (N!=0 || M!=0) {

			// Where we will store our answers.
			long[][] memo = new long[N][M+1];
			for (int i=0; i<N; i++)
					Arrays.fill(memo[i], -1);

			// Get the sequence.
			int[] seq = new int[N];
			for (int i=0; i<N; i++)
				seq[i] = stdin.nextInt();

			// Fill in base cases with no tracks destroyed.
			long[][] memo2 = new long[N][N];
			for (int i=0; i<N; i++)
				fillmax(seq, memo2, i);

			System.out.println(solve(memo, memo2, 0, M));

			N = stdin.nextInt();
			M = stdin.nextInt();
		}
	}

	// Returns the score of the sequence seq[start...end] with no
	// tracks destroyed.
	public static void fillmax(int[] seq, long[][] memo2, int end) {

		int sum = 0;

		// Now we don't have to do an n^2 loop...
		int ans = 0;
		for (int i=end; i>=0; i--) {
			ans = ans + seq[i]*sum;
			memo2[i][end] = ans;
			sum = sum + seq[i];
		}

	}

	// Returns the lowest score for seq[start...end] broken in splits number of places.
	public static long solve(long[][] memo, long[][] memo2, int start, int splits) {

		int N = memo.length;
		
		// Out of bounds.
		if (start >= N-1)
			return 0;
			
		// No place to split.
		if (splits == 0)
			return memo2[start][memo2[0].length-1];

		// We previously calculated this case.
		if (memo[start][splits] != -1)
			return memo[start][splits];

		// Save overestimate.
		long best = (1L << 62);

		// gap represents where we will mark our first railroad split.
		for (int gap = start; gap<N; gap++) {

			// Score is first segment plus the rest, that start at gap+1.
			// For the rest, we must have splits-1 splits.
			long curscore = memo2[start][gap] + solve(memo, memo2, gap+1, splits-1);
			if (curscore < best)
				best = curscore;

			// If this one segment is too much, no point in checking the rest.
			if (memo2[start][gap] > best)
				break;
		}

		// Store the answer and return.
		memo[start][splits] = best;
		return best;

	}
}