第七届“腾讯云杯”上海高校金马程序设计联赛暨东华大学校赛邀请赛（网络同步赛）

佩奇开着她自制的迷你小飞机来参加一个游戏。这个游戏中有一块 $1\times N$ 大小的铺着瓷砖的区域，这个区域由 $N$ 块 $1\times 1$ 大小的正方形瓷砖从左到右依次拼接而成。其中，每块瓷砖中心的正上方1m处都有一个小礼品，每个礼品都有一个价值。

如下图所示，佩奇开着她的小飞机从左边第 $1$ 块瓷砖的中心点向右出发，最后必须停止在右边第 $1$ 块瓷砖的中心点。由于她自己造的迷你小飞机还在初步研发阶段，功能十分有限，只有起飞、平行于地面飞行、降落这 $3$ 个功能。每个功能详细情况如下：

1. 起飞时，只能向图片中的右上方飞行，仰角固定为 45°，飞行目标高度固定为1m;
2. 平行于地面飞行时，只能往图片正右方飞行，飞行高度固定为$1$ ，每次起飞后平行飞行的距离不超过 $K$（平行飞行阶段的飞行距离是一个不超过 $K$ 的非负整数，每次降落又重新起飞后，平行飞行距离重新计数）;
3. 降落时，只能向图片中的右下方飞行，俯角固定为 45°，降落目标为右下方瓷砖的中心点，降落高度固定为 $1$。

当佩奇在飞行过程中经过某些礼品时，她就能拿到这些礼品。佩奇想要知道她能获得的礼品价值总和最大是多少？

备注：上图为样例 #1 对应的图例， $K=3$ 时，飞机每次起飞后佩奇可以拿到最多 $K+1=4$ 个小礼品。经过 $3$ 次起飞与降落，佩奇最多能获得价值 $7+3+9+8+10+6+9+11=63$ 的礼品。注意，佩奇的小飞机在地面上不能滑行或移动，只能在每块瓷砖的中心点停歇。