#include <bits/stdc++.h>
using namespace std;
 
int main() 
{
	int n;
	cin >> n;
	vector<int> costs(n);
	for(int &x : costs)
		cin >> x;
	int weeks;
	cin >> weeks;
 
	vector<vector<int>> dp(n+1,vector<int>(weeks + 1, 1e9));
	//dp[i][w] - min cost to partition first i costs in w weeks 
 
	dp[0][0] = 0; //base case
 
	for(int w = 1 ; w <= weeks ; w++)
	{
		for(int i = w ; i <= n ; i++)
		{
			int mx = 0; //cost for thsi partition
			for(int j = i - 1 ; j >= w - 1 ; j--)
			{
				mx = max(mx,costs[j]);
 
				dp[i][w] = min(dp[i][w],
								dp[j][w-1] + mx);
			}
		}
	}
	cout << dp[n][weeks] << "\n";
 
	return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbWFpbigpIAp7CglpbnQgbjsKCWNpbiA+PiBuOwoJdmVjdG9yPGludD4gY29zdHMobik7Cglmb3IoaW50ICZ4IDogY29zdHMpCgkJY2luID4+IHg7CglpbnQgd2Vla3M7CgljaW4gPj4gd2Vla3M7CgkKCXZlY3Rvcjx2ZWN0b3I8aW50Pj4gZHAobisxLHZlY3RvcjxpbnQ+KHdlZWtzICsgMSwgMWU5KSk7CgkvL2RwW2ldW3ddIC0gbWluIGNvc3QgdG8gcGFydGl0aW9uIGZpcnN0IGkgY29zdHMgaW4gdyB3ZWVrcyAKCQoJZHBbMF1bMF0gPSAwOyAvL2Jhc2UgY2FzZQoJCglmb3IoaW50IHcgPSAxIDsgdyA8PSB3ZWVrcyA7IHcrKykKCXsKCQlmb3IoaW50IGkgPSB3IDsgaSA8PSBuIDsgaSsrKQoJCXsKCQkJaW50IG14ID0gMDsgLy9jb3N0IGZvciB0aHNpIHBhcnRpdGlvbgoJCQlmb3IoaW50IGogPSBpIC0gMSA7IGogPj0gdyAtIDEgOyBqLS0pCgkJCXsKCQkJCW14ID0gbWF4KG14LGNvc3RzW2pdKTsKCQkJCQoJCQkJZHBbaV1bd10gPSBtaW4oZHBbaV1bd10sCgkJCQkJCQkJZHBbal1bdy0xXSArIG14KTsKCQkJfQoJCX0KCX0KCWNvdXQgPDwgZHBbbl1bd2Vla3NdIDw8ICJcbiI7CgkKCXJldHVybiAwOwp9

OAoyIDUgNCAzIDcgMSA2IDgKMw==

8
2 5 4 3 7 1 6 8
3