给定一个由 行构成的数字三角形。第 行共有 个整数，整体形状如下图所示（以 为例）： 从顶点（第一行唯一的数字）出发，依次向下移动恰好 次直到抵达最后一行。 假设当前位于第 行第 列： 可以向正下方移动至第 行第 列； 可以向左下方移动至第 行第 列； 可以向右下方移动至第 行第 列。 每到达一个位置都会获得该位置的数值。定义在整个行走过程中，向左下方移动的次数记为 ，向右下方移动的次数记为 。我们需要满足 请你选择一条合法路径，使得获得数值之和最大，并输出该最大值。

输入描述:

在一行上输入两个整数 ，分别表示数字三角形的行数与允许的移动差。 此后 行，第 行输入 个整数 共计 个整数。

输出描述:

输出一个整数，表示满足条件的路径可以取得的最大数值之和。