import java.util.Scanner; public class Main { public static void main(String[] args) { final long INF = -1_000_000_000_000_000_000L; Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); // 初始化数字三角形数组 long[][] nums = new long[n][]; for (int i = 0; i < n; i++) { nums[i] = new long[2 * i + 1]; for (int j = 0; j < 2 * i + 1; j++) { nums[i][j] = sc.nextLong(); } } // 初始化dp数组 long[][] dp = new long[n][]; for (int i = 0; i < n; i++) { dp[i] = new long[2 * i + 1]; } // 数字三角形数组最后一行(n-1)行赋值 int center = n - 1; for (int j = 0; j < 2 * n - 1; j++) { if (Math.abs(j - center) <= k) { dp[n - 1][j] = nums[n - 1][j]; } else { dp[n - 1][j] = INF; } } // 从下向上递推 for (int i = n - 2; i >= 0; i--) { for (int j = 0; j <= 2 * i; j++) { long maxNext = Math.max(dp[i + 1][j], Math.max(dp[i + 1][j + 1], dp[i + 1][j + 2])); if (maxNext > INF) { dp[i][j] = nums[i][j] + maxNext; } else { dp[i][j] = INF; } } } System.out.println(dp[0][0]); } }