/* package whatever; // don't place package name! */
 
import java.util.*;
import java.lang.*;
import java.io.*;
 
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
	int[] A = {8, 1, 9, 2, 7};
	int k = 3;
 
	int n = A.length;
	int[][] dp = new int[n + 1][k+ 1];
 
	for(int i = 0; i <= n; i++){
		Arrays.fill(dp[i], Integer.MAX_VALUE);
	}
 
	// for(int i = 0; i <= k; i++){
	// dp[0][i] = 0;
	// }
	dp[0][0] = 0;
 
	for(int i = 1; i <= n; i++){
		for(int parts = 1; parts <= k; parts++){
			int maxSlot = 0;
 
			for(int j = i; j >= 1; j--){
				maxSlot = Math.max(maxSlot, A[j - 1]);
 
				if(dp[j-1][parts-1] != Integer.MAX_VALUE){
					dp[i][parts] = Math.min(dp[i][parts], maxSlot + dp[j - 1][parts - 1]);
				}
			}
		}
	}
 
	System.out.print(dp[n][k]);
	}
}

LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbgoJewoJCS8vIHlvdXIgY29kZSBnb2VzIGhlcmUKCWludFtdIEEgPSB7OCwgMSwgOSwgMiwgN307CglpbnQgayA9IDM7CgkKCWludCBuID0gQS5sZW5ndGg7CglpbnRbXVtdIGRwID0gbmV3IGludFtuICsgMV1baysgMV07CgkKCWZvcihpbnQgaSA9IDA7IGkgPD0gbjsgaSsrKXsKCQlBcnJheXMuZmlsbChkcFtpXSwgSW50ZWdlci5NQVhfVkFMVUUpOwoJfQoJCgkvLyBmb3IoaW50IGkgPSAwOyBpIDw9IGs7IGkrKyl7CgkvLyBkcFswXVtpXSA9IDA7CgkvLyB9CglkcFswXVswXSA9IDA7CgkKCWZvcihpbnQgaSA9IDE7IGkgPD0gbjsgaSsrKXsKCQlmb3IoaW50IHBhcnRzID0gMTsgcGFydHMgPD0gazsgcGFydHMrKyl7CgkJCWludCBtYXhTbG90ID0gMDsKCQkJCgkJCWZvcihpbnQgaiA9IGk7IGogPj0gMTsgai0tKXsKCQkJCW1heFNsb3QgPSBNYXRoLm1heChtYXhTbG90LCBBW2ogLSAxXSk7CgkJCQkgCgkJCQlpZihkcFtqLTFdW3BhcnRzLTFdICE9IEludGVnZXIuTUFYX1ZBTFVFKXsKCQkJCQlkcFtpXVtwYXJ0c10gPSBNYXRoLm1pbihkcFtpXVtwYXJ0c10sIG1heFNsb3QgKyBkcFtqIC0gMV1bcGFydHMgLSAxXSk7CgkJCQl9CgkJCX0KCQl9Cgl9CgkKCVN5c3RlbS5vdXQucHJpbnQoZHBbbl1ba10pOwoJfQp9