题目描述
小同学非常喜欢三角形，现在他想出个题目给小R同学做，想要考考小R同学。
题目是这样的，给你一个数字三角形，第一行1个数字，第二行3个数字，第i行2*i―1个数字，一共n行。如下图所示，为3行的数字三角形，一开始从顶点出发，当位于某一点时可以往这个点的正下方走，也可以往左下方和右下方走。
例如在值为3的这一个点，可以往正下方走到7，也可以往左下方走到6，也可往右下方走到8(不能从3走到5或9) 。
每走到一个位置就会取出当前所在位置的值，问从顶点走到最后一层，最终的往左下方和往右下方的次数之差的绝对值不能超过k次，所取的数值总和的最大值为多少。
题目是这样的，给你一个数字三角形，第一行1个数字，第二行3个数字，第i行2*i―1个数字，一共n行。如下图所示，为3行的数字三角形，一开始从顶点出发，当位于某一点时可以往这个点的正下方走，也可以往左下方和右下方走。
例如在值为3的这一个点，可以往正下方走到7，也可以往左下方走到6，也可往右下方走到8(不能从3走到5或9) 。
每走到一个位置就会取出当前所在位置的值，问从顶点走到最后一层，最终的往左下方和往右下方的次数之差的绝对值不能超过k次，所取的数值总和的最大值为多少。
输入
第一行输入n，k，1≤n ≤300,0≤k ≤300, k ≤n
接下来输入n行，第i行共2*i―1个值，对于每个值x, -2* 1e9<x≤2* 1e9
接下来输入n行，第i行共2*i―1个值，对于每个值x, -2* 1e9<x≤2* 1e9
输出
输出从顶点到底部的获取总和的最大值
样例输入 Copy
3 1
1
2 3 4
5 6 7 8 9
样例输出 Copy
13
提示
第一次在值为1的点，第二次向右下方走到值为4，第三次从4这个点往正下方走到值为8的点，总和为13