N, K = map(int, input().split())
nums = list(map(int, input().split()))
def solve_lambda(penalty):
# dp = [[0, 0] for _ in range(N)]
# count = [[0, 0] for _ in range(N)]
dp_prev0 = 0
count_prev0 = 0
dp_prev1 = nums[0] - penalty
count_prev1 = 1
# dp[0][1] = nums[0] - penalty
# count[0][1] = 1
for i in range(1, N):
(dp0, count0) = max(
(dp_prev0, count_prev0),
(dp_prev1, count_prev1),
)
(dp1, count1) = max(
(dp_prev0 + nums[i] - penalty, count_prev0 + 1),
(dp_prev1 + nums[i], count_prev1)
)
dp_prev0, dp_prev1 = dp0, dp1
count_prev0, count_prev1 = count0, count1
return max(
(dp0, count0),
(dp1, count1)
)
lo = 0
hi = sum(map(abs, nums)) + 1
while lo < hi - 1:
mid = (lo + hi) // 2
penalised, count = solve_lambda(mid)
if count >= K:
lo = mid
else:
hi = mid
penalised, count = solve_lambda(lo)
print(penalised + K * lo)
