该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

YJ大一时怀着满腔热情刷题，希望能够加入ACM集训队，却很快在深不见底的知识海洋中感到了窒息。当她几乎要放弃时，一位特别的“网友”出现了——他是一位小猫咪学长。

“yjtql！” ​——这是小猫咪学长的招牌鼓励。无论多晚，只要YJ在QQ提问，总能收到他秒回的长篇解答。他的QQ头像，成了YJ深夜刷题时最温暖的光。

最难忘的，是那个关于“棋子”的深夜。 一道DFS+状态记录的题目，YJ的代码始终有一个边界条件无法通过。已经凌晨一点，小猫咪学长说：“没事，要有信心”他们一行行调试。当终于AC时，窗外已晨光微熹。学长发来一条消息：“好好学习，冲！”

他不仅教算法，更教她勇敢。 当ACM集训队队长竞选时，YJ这个“社恐”根本不敢报名。小猫咪学长对她说：“YJ速当集训队队长，加油！。”虽然最终落选，但完成竞选演讲的那一刻，YJ感觉自己真正地蜕变了。

“要像学长帮我一样，去帮下一届的学弟学妹。”——这成了YJ内心最坚定的信念。小猫咪学长在她身上种下的不只是算法知识，更是一种关于传承的精神。

如今，YJ已经能独立解决很多难题，为了纪念小猫咪学长与自己的经历，YJ想用一道特别的题目来纪念这段特殊的缘分——

“学长，你就像我的‘初始化参数’，定义了我对ACM所有的热爱与坚持。现在，请让我用你教给我的一切，为你出一道题。”

题目描述

给定一个 n×n 的棋盘，YJ的棋子从左上角 (1,1) 出发，要走到右下角 (n,n)。棋子只能向右或向下移动。

每个格子有一个感恩值（1-9的整数）。YJ定义一条路径的感恩度为路径上所有格子的感恩值之和。

但是，YJ想要寻找的是一条特殊的路径：

• 路径必须经过恰好 k 个"偶数感恩值"的格子（感恩值为2、4、6、8的格子）
• 在满足条件的路径中，感恩度最大的那条路径的感恩度是多少？

Format

输入格式

• 第一行：n k (2 ≤ n ≤ 8, 0 ≤ k ≤ n×n-2)
• 接下来n行，每行n个整数，表示棋盘的感恩值矩阵

输出格式

• 一个整数，表示最大感恩度。如果不存在满足条件的路径，输出-1

Samples

3 2
1 2 3
4 5 6
7 8 9

29

样例解释 路径：1→4→7→8→9

• 感恩值：1+4+7+8+9 = 29
• 偶数格子：4和8，共2个，满足k=2的要求

Limitation

1s, 1024KiB for each test case.