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]);
}
}