/* 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[] arr = {2,6,9,7,8};
		int n = arr.length;
 
		int[][] dp = new int[n+1][n+1];
 
		int sum = 0;
 
		for(int i = 0; i < n; i++){
			dp[i][i] = 0;
			sum += arr[i];
		}
 
		for(int i = 0; i < n - 1; i++){
			dp[i][i+1] = arr[i] + arr[i+1];
		}
 
		for(int len = 3; len <= n; len++){
			for(int i = 0; i <= n - len; i++){
				int j = i + len - 1;
				int min = Integer.MAX_VALUE;
 
				for(int k = i; k < j; k++){
					min = Math.min(min, dp[i][k] + dp[k+1][j] + sum);
				}
 
				dp[i][j] = min;
			}
		}
 
		System.out.print(dp[0][n-1]);
	}
}

LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbgoJewoJCS8vIHlvdXIgY29kZSBnb2VzIGhlcmUKCQlpbnRbXSBhcnIgPSB7Miw2LDksNyw4fTsKCQlpbnQgbiA9IGFyci5sZW5ndGg7CgkJCgkJaW50W11bXSBkcCA9IG5ldyBpbnRbbisxXVtuKzFdOwoJCQoJCWludCBzdW0gPSAwOwoJCQoJCWZvcihpbnQgaSA9IDA7IGkgPCBuOyBpKyspewoJCQlkcFtpXVtpXSA9IDA7CgkJCXN1bSArPSBhcnJbaV07CgkJfQoJCQoJCWZvcihpbnQgaSA9IDA7IGkgPCBuIC0gMTsgaSsrKXsKCQkJZHBbaV1baSsxXSA9IGFycltpXSArIGFycltpKzFdOwoJCX0KCQkKCQlmb3IoaW50IGxlbiA9IDM7IGxlbiA8PSBuOyBsZW4rKyl7CgkJCWZvcihpbnQgaSA9IDA7IGkgPD0gbiAtIGxlbjsgaSsrKXsKCQkJCWludCBqID0gaSArIGxlbiAtIDE7CgkJCQlpbnQgbWluID0gSW50ZWdlci5NQVhfVkFMVUU7CgkJCQkKCQkJCWZvcihpbnQgayA9IGk7IGsgPCBqOyBrKyspewoJCQkJCW1pbiA9IE1hdGgubWluKG1pbiwgZHBbaV1ba10gKyBkcFtrKzFdW2pdICsgc3VtKTsKCQkJCX0KCQkJCQoJCQkJZHBbaV1bal0gPSBtaW47CgkJCX0KCQl9CgkJCgkJU3lzdGVtLm91dC5wcmludChkcFswXVtuLTFdKTsKCX0KfQ==