def solve(N, M, a):
    INF = float('inf')
    dp = [[-INF] * (N + 1) for _ in range(M)]
    total_sum = sum(a)

    def recursive(i, left, right, turn):
        if left > right:
            return 0
        
        segment_length = right - left + 1
        if dp[turn][segment_length] != -INF:
            return dp[turn][segment_length]
        
        dp[turn][segment_length] = max(a[left] + recursive(i + 1, left + 1, right, turn - 1), 
                                       a[right] + recursive(i + 1, left, right - 1, turn - 1))
        
        return dp[turn][segment_length]

    return recursive(0, 0, N - 1, M - 1)