/* 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
	{
		int[] price = {1, 5, 8, 9, 10, 22, 17, 20, 24, 30};
		int N = price.length;
		int K = 3;
		int[][] D = new int[N+1][K+1];
 
		for (int n = 1; n <= N; n++)
			D[n][0] = price[n-1];
 
		for (int k = 1; k <= K; k++)
		for (int n = 0; n <= N; n++)
		for (int i = 0; i <= n-1; i++)
			D[n][k] = Math.max(D[n][k], price[i] + D[n-i-1][k-1]);
 
		int best = 0;
		for (int k = 0; k <= K; k++)
			best = Math.max(best, D[N][k]);
 
		System.out.println(best);
	}
}

LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbgoJewoJCWludFtdIHByaWNlID0gezEsIDUsIDgsIDksIDEwLCAyMiwgMTcsIDIwLCAyNCwgMzB9OwoJCWludCBOID0gcHJpY2UubGVuZ3RoOwoJCWludCBLID0gMzsKCQlpbnRbXVtdIEQgPSBuZXcgaW50W04rMV1bSysxXTsKCQkKCQlmb3IgKGludCBuID0gMTsgbiA8PSBOOyBuKyspCgkJCURbbl1bMF0gPSBwcmljZVtuLTFdOwoKCQlmb3IgKGludCBrID0gMTsgayA8PSBLOyBrKyspCgkJZm9yIChpbnQgbiA9IDA7IG4gPD0gTjsgbisrKQoJCWZvciAoaW50IGkgPSAwOyBpIDw9IG4tMTsgaSsrKQoJCQlEW25dW2tdID0gTWF0aC5tYXgoRFtuXVtrXSwgcHJpY2VbaV0gKyBEW24taS0xXVtrLTFdKTsKCgkJaW50IGJlc3QgPSAwOwoJCWZvciAoaW50IGsgPSAwOyBrIDw9IEs7IGsrKykKCQkJYmVzdCA9IE1hdGgubWF4KGJlc3QsIERbTl1ba10pOwoKCQlTeXN0ZW0ub3V0LnByaW50bG4oYmVzdCk7Cgl9Cn0=