import java.util.*;
import java.io.*;
import java.io.BufferedReader;
import java.awt.Point;

public class cbarn{
	public static final String TASKNAME = "cbarn";
	public static long mod= 1000000007;
	public static Debug db;

	public static void main(String[] args) throws IOException {
		InputReader in = new InputReader(System.in);
		PrintWriter out = new PrintWriter(System.out);
		//		InputReader in = new InputReader(new FileInputStream(TASKNAME+".in"));
		//		PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(TASKNAME+".out")));
		Autocompletion solver = new Autocompletion();
		db=new Debug(System.getSecurityManager()==null);
		solver.solve(1, in, out);
		out.close();
	}
	static class Autocompletion {
		int rot;
		int N, K;
		int MAXN=1010;
		int MAXK=10;
		int a[]=new int[MAXN];
		long A[]=new long[MAXN];
		long DP[][]=new long[MAXK][MAXN];
		long WSUM[][]=new long[MAXN][MAXN];
		long INF=Long.MAX_VALUE;
		public void solve(int testNumber, InputReader in, PrintWriter out) {
			N=in.nextInt();
			K=in.nextInt();
			a=in.nextIntArr(N);
			for(int i=0;i<N;i++) {
				A[i]=a[N-1-i];
			}
			for (int i = 0; i < N; i++) {
				long sm = 0;
				for (int j = 1; j <= N; j++) {
					WSUM[i][j] = WSUM[i][j - 1] + sm;
					sm += A[madd(i, j - 1)];
				}
			}
			long result = INF;
			for(int i=0;i<DP.length;i++) {
				Arrays.fill(DP[i], Long.MAX_VALUE);
			}

			//			  memset(DP, 0x3F, sizeof(DP));
			DP[0][N] = 0;
			for (rot = 0; rot < N; rot++) {
				for (int i = 1; i <= K; i++) {
					solve(i, 0, N, 1, N + 1);
				}
				result = Math.min(result, DP[K][0]);
			}
			out.println(result);
		}
		int madd(int x, int y) {
			x += y;
			if (x >= N) {
				x -= N;
			}
			return x;
		}

		long wsum(int a, int b) {
			return WSUM[madd(a, rot)][madd(b, N - a)];
		}

		void solve(int k, int ia, int ib, int ja, int jb) {
			if (ia == ib) {
				return;
			}

			int i = (ia + ib) / 2;
			int arg_j = -1;

			DP[k][i] = INF;
			for (int j = Math.max(i + 1, ja); j < jb; j++) {
				long v = wsum(i, j) + DP[k - 1][j];
				if (v < DP[k][i]) {
					arg_j = j;
					DP[k][i] = v;
				}
			}

			solve(k, ia, i, ja, arg_j + 1);
			solve(k, i + 1, ib, arg_j, jb);
		}
	}
	static class Pair implements Comparable<Pair>{
		int x;
		int y;
		Pair(int a, int b){
			x=a;
			y=b;
		}
		@Override
		public int compareTo(Pair arg0) {
			if(arg0.x!=x)return x-arg0.x;
			return y-arg0.y;
		}
	}
	static class Triple implements Comparable<Triple>{
		int x;
		int y;
		int z;
		Triple(int a, int b, int c){
			x=a;
			y=b;
			z=c;
		}
		@Override
		public int compareTo(Triple arg0) {
			if(arg0.x!=x)return x-arg0.x;
			return y-arg0.y;
		}
	}

	static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
		public int[] nextIntArr(int n) {
			int arr[]=new int[n];
			for(int i=0;i<n;i++) {
				arr[i]=this.nextInt();
			}
			return arr;
		}
	}
	public static class Debug {
		private boolean allowDebug;

		public Debug(boolean allowDebug) {
			this.allowDebug = allowDebug;
		}

		private void outputName(String name) {
			System.out.print(name + " = ");
		}

		public void debug(String name, int x) {
			if (!allowDebug) {
				return;
			}

			outputName(name);
			System.out.println("" + x);
		}

		public void debug(String name, long x) {
			if (!allowDebug) {
				return;
			}
			outputName(name);
			System.out.println("" + x);
		}

		public void debug(String name, double x) {
			if (!allowDebug) {
				return;
			}
			outputName(name);
			System.out.println("" + x);
		}

		public void debug(String name, int[] x) {
			if (!allowDebug) {
				return;
			}
			outputName(name);
			System.out.println(Arrays.toString(x));
		}

		public void debug(String name, long[] x) {
			if (!allowDebug) {
				return;
			}
			outputName(name);
			System.out.println(Arrays.toString(x));
		}

		public void debug(String name, double[] x) {
			if (!allowDebug) {
				return;
			}
			outputName(name);
			System.out.println(Arrays.toString(x));
		}

		public void debug(String name, Pair[] x) {
			if (!allowDebug) {
				return;
			}
			outputName(name);
			StringBuilder sb = new StringBuilder("[");
			int cnt=0;
			for(Pair y:x) {
				sb.append('('+y.x+","+y.y+')');
				if (cnt != x.length-1)sb.append(", ");
				cnt++;
			}
			System.out.println(sb.append("]").toString());
		}

		public void debug(String name, Object x) {
			if (!allowDebug) {
				return;
			}
			outputName(name);
			System.out.println("" + x);
		}

		public void debug(String name, Object... x) {
			if (!allowDebug) {
				return;
			}
			outputName(name);
			System.out.println(Arrays.deepToString(x));
		}
	}
}