// Source: https://usaco.guide/general/io import java.io.*; import java.util.*; public class feast { static int n, k; static long[] a; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); n = Integer.parseInt(st.nextToken()); k = Integer.parseInt(st.nextToken()); a = new long[n]; st = new StringTokenizer(br.readLine()); for(int i = 0; i < n; i++) a[i] = Long.parseLong(st.nextToken()); long low = 0; long high = 300000000000000L; long ans = 0; while(low <= high) { long mid = low + (high - low) / 2; long[] res = solve(mid); if(res[1] <= k) { ans = res[0] + mid * k; high = mid - 1; } else low = mid + 1; } System.out.println(ans); } private static long[] solve(long n) { long dp0 = 0; int c0 = 0; long dp1 = -1000000000000000000L; int c1 = 0; for(long i: a) { long next_dp0; int next_c0; if(dp0 > dp1) { next_dp0 = dp0; next_c0 = c0; } else if (dp1 > dp0) { next_dp0 = dp1; next_c0 = c1; } else { next_dp0 = dp0; next_c0 = Math.min(c0, c1); } long extend_val = dp1 + i; long start_val = dp0 + i - n; long next_dp1; int next_c1; if(extend_val > start_val) { next_dp1 = extend_val; next_c1 = c1; } else if (start_val > extend_val) { next_dp1 = start_val; next_c1 = c0 + 1; } else { next_dp1 = extend_val; next_c1 = Math.min(c1, c0 + 1); } dp0 = next_dp0; c0 = next_c0; dp1 = next_dp1; c1 = next_c1; } if(dp0 > dp1) return new long[]{dp0, c0}; if(dp1 > dp0) return new long[]{dp1, c1}; return new long[]{dp0, Math.min(c0, c1)}; } }