2018 研究生面试机考 (软件工程)

港岛妹妹，你献给我的西班牙馅饼
甜蜜地融化了我，天空之城在哭泣
港岛妹妹，我们曾拥有的甜蜜的爱情
疯狂地撕裂了我，天空之城在哭泣

——李志《天空之城》

粉丝问：“我想问一下在你歌词里面的馅饼是什么？”

李志答：“告诉你，西班牙馅饼是怎么一回事。是有一次我一个朋友给我寄了一张明信片，从西班牙寄过来的，明信片的封面是一块馅饼，谢谢你，你惊讶吗？你们惊讶吗？想想啥？你们知道个几把？整天瞎几把猜对不对？挺可笑的。所以答案一公布就这个样子。你再回想一下生活里面有多少个这样的事情，你充满了幻想，充满了好奇，猜哦，瞎几把猜，猜到后面傻逼了吧？没猜到了吧？”

现在我们看见了这个西班牙馅饼长什么样，西班牙馅饼是个矩形形状，想不到吧。我们可以把它抽象成一个 $N$ 行 $M$ 列的正整数矩阵。每个格子有一个“美味值”，由于一些不可告人的原因我们对于这个馅饼没行只能吃一口，港岛妹妹说如果她吃到美味值为 $k$ 的馅饼，就会给我做出美味值为 $k$ 的红烧肉。问红烧肉最多能有多好吃。