贪吃蛇

题号：NC266136
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

一个 $6\times 6$ 的网格上进行贪吃蛇游戏，左上角为 $(1,1)$ ，右下角为 $(6,6)$ 。初始情况下，一条长度为 $k$ 的贪吃蛇水平存在于网格上，初始方向向右，蛇头位于 $(1,k)$ ，蛇尾位于 $(1,1)$ 。

例如初始长度为 $5$ ，情况如下：

除此之外，还有 $n$ 个食物，第 $i$ 个食物位于 $(x_i,y_i)$ ，美味值为 $val_i$ ，一个食物最多只能吃一次。

贪吃蛇每一步可以沿着当前方向继续往前走一格，或者改变当前方向之后（对于蛇头前进方向的左转或者右转）往前一格。

如果超出了地图，会从对侧继续延申，和现实贪吃蛇游戏一样，例如 $(1,6)$ ，方向为右，继续当前方向走一格出现在 $(1,1)$ 。

每一次蛇头往前一格时，如果没有吃到食物，蛇尾也会向前一格；否则，蛇身延长一格，蛇尾停留在上次的位置。

例如：贪吃蛇蛇头右转，往前一格吃食物，如下图

吃掉食物后，贪吃蛇的分布情况如下：

初始情况下，食物不会出现在蛇身任一位置。

如果咬到蛇身，游戏直接结束，蛇头和蛇尾一起行动，也就是说蛇头下一步走到当前蛇尾位置，不会咬到。

现在要求贪吃蛇最多只能转向 $cnt$ 次，问能吃到的食物美味值总和最大是多少？

第一行包含三个整数 $1 \leq n \leq 36-k,1 \leq k \leq 6,1 \leq cnt \leq 5$ ，含义和题目描述一致。

接下来 $n$ 行，每行三个整数 $1 \leq x_i,y_i \leq 6,1 \leq val_i \leq 10^6$ ，数据保证一个坐标最多只有一个食物。

输出一行一个整数，表示获得的最大美味值。

示例1

复制

复制

样例图示：

可行方案：