using System.Diagnostics; class Program { static string ReadLine() => Console.ReadLine().Trim(); static int ReadInt() => int.Parse(ReadLine()); static long ReadLong() => long.Parse(ReadLine()); static int[] ReadIntArray() { string str = ReadLine(); return str != "" ? str.Split().Select(_ => int.Parse(_)).ToArray() : new int[0]; } static long[] ReadLongArray() { string str = ReadLine(); return str != "" ? str.Split().Select(_ => long.Parse(_)).ToArray() : new long[0]; } static (int, int) ReadInt2() { int[] vs = ReadIntArray(); return (vs[0], vs[1]); } static (int, int, int) ReadInt3() { int[] vs = ReadIntArray(); return (vs[0], vs[1], vs[2]); } static (int, int, int, int) ReadInt4() { int[] vs = ReadIntArray(); return (vs[0], vs[1], vs[2], vs[3]); } static (int, int, int, int, int) ReadInt5() { int[] vs = ReadIntArray(); return (vs[0], vs[1], vs[2], vs[3], vs[4]); } static (long, long) ReadLong2() { long[] vs = ReadLongArray(); return (vs[0], vs[1]); } static (long, long, long) ReadLong3() { long[] vs = ReadLongArray(); return (vs[0], vs[1], vs[2]); } static (long, long, long, long) ReadLong4() { long[] vs = ReadLongArray(); return (vs[0], vs[1], vs[2], vs[3]); } static void Main() { SourceExpander.Expander.Expand(); (int N, int K) = ReadInt2(); long[] A = ReadLongArray(); long[,] dp = new long[K + 1, 2]; for (int i = 0; i < K + 1; i++) { dp[i, 0] = long.MinValue; dp[i, 1] = long.MinValue; } dp[0, 0] = 0; for (int i = 0; i < N; i++) { long v = A[i]; long[,] n_dp = (long[,])dp.Clone(); for (int j = 0; j <= K; j++) { if (dp[j, 0] != long.MinValue) { if (j + 1 <= K && n_dp[j + 1, 1] < dp[j, 0] + v) n_dp[j + 1, 1] = dp[j, 0] + v; } if (dp[j, 1] != long.MinValue) { if (n_dp[j, 0] < dp[j, 1]) n_dp[j, 0] = dp[j, 1]; } } dp = n_dp; } long ans = Math.Max(dp[K, 0], dp[K, 1]); if(ans > long.MinValue) Console.WriteLine(ans); else Console.WriteLine("Impossible"); } void F11() { (int N, int K) = ReadInt2(); long[] A = ReadLongArray(); long[] dp = new long[K + 1]; for (int i = 0; i < N; i++) { long v = A[i]; long[] n_dp = (long[])dp.Clone(); for (int j = 0; j <= K; j++) { if (j + 1 <= K && n_dp[j + 1] < dp[j] + v) n_dp[j + 1] = dp[j] + v; if (n_dp[j] < dp[j]) n_dp[j] = dp[j]; } dp = n_dp; } //Console.WriteLine(dp.Max()); } } #region Expanded by https://github.com/kzrnm/SourceExpander namespace SourceExpander{public class Expander{[Conditional("EXP")]public static void Expand(string inputFilePath=null,string outputFilePath=null,bool ignoreAnyError=true){}public static string ExpandString(string inputFilePath=null,bool ignoreAnyError=true){return "";}}} #endregion Expanded by https://github.com/kzrnm/SourceExpander