#include <iostream>
#define INF 1000000000
using namespace std;
 
int n, m, dist[100] = {1,5,2,6,8,3,2}, dp[1000][1000];
 
int solve(int index, int count){
	if(index == n){
		if(count == m) return 0;
		else return INF;
	}
	if(dp[index][count] != -1) return dp[index][count];
	int sum = 0, ans = INF;
	for(int i = index;i < n;i++){
		sum += dist[i];
		int val = max(sum, solve(i+1, count+1));
		ans = min(ans, val);
	}
	return dp[index][count] = ans;
}
 
int main() {
	// your code goes here
	n = 7, m = 3;
	for(int i = 0;i < 1000;i++) for(int j = 0;j < 1000;j++) dp[i][j] = -1;
	cout << solve(0, 0) << endl;
	return 0;
}
 

I2luY2x1ZGUgPGlvc3RyZWFtPgojZGVmaW5lIElORiAxMDAwMDAwMDAwCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbiwgbSwgZGlzdFsxMDBdID0gezEsNSwyLDYsOCwzLDJ9LCBkcFsxMDAwXVsxMDAwXTsKCmludCBzb2x2ZShpbnQgaW5kZXgsIGludCBjb3VudCl7CglpZihpbmRleCA9PSBuKXsKCQlpZihjb3VudCA9PSBtKSByZXR1cm4gMDsKCQllbHNlIHJldHVybiBJTkY7Cgl9CglpZihkcFtpbmRleF1bY291bnRdICE9IC0xKSByZXR1cm4gZHBbaW5kZXhdW2NvdW50XTsKCWludCBzdW0gPSAwLCBhbnMgPSBJTkY7Cglmb3IoaW50IGkgPSBpbmRleDtpIDwgbjtpKyspewoJCXN1bSArPSBkaXN0W2ldOwoJCWludCB2YWwgPSBtYXgoc3VtLCBzb2x2ZShpKzEsIGNvdW50KzEpKTsKCQlhbnMgPSBtaW4oYW5zLCB2YWwpOwoJfQoJcmV0dXJuIGRwW2luZGV4XVtjb3VudF0gPSBhbnM7Cn0KCmludCBtYWluKCkgewoJLy8geW91ciBjb2RlIGdvZXMgaGVyZQoJbiA9IDcsIG0gPSAzOwoJZm9yKGludCBpID0gMDtpIDwgMTAwMDtpKyspIGZvcihpbnQgaiA9IDA7aiA8IDEwMDA7aisrKSBkcFtpXVtqXSA9IC0xOwoJY291dCA8PCBzb2x2ZSgwLCAwKSA8PCBlbmRsOwoJcmV0dXJuIDA7Cn0K