#86. 「2023 新生杯」无意识哲学

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: woruo

题目描述

猫猫冒险队来到 Koishi 的王座前,只见 Koishi 打了个响指,四周便出现了巨大的火墙包围着 Koishi 与猫猫冒险队,仿佛像是早已准备好的战斗舞台。

战斗舞台是一个矩形,且里面正好有 行, 列地板(行和列都从 开始编号)。

战斗舞台上有 个炸药桶,第 个炸药桶的位置在第 行,第 列地板上,且爆炸半径为

炸药桶的爆炸范围是一个矩形。准确来说,假设某块地板在战斗舞台的第 行,第 列,第 个炸药桶会炸到战斗舞台内所有同时满足以下两个条件的所有地板:

某个炸药桶爆炸后会引爆自身爆炸范围内的所有炸药桶,被引爆的炸药桶可以继续引爆自身爆炸范围内的所有炸药桶。

由于 Koishi 拥有无意识的能力,她会等概率的随机出现在战斗舞台中某一块地板上,且猫猫冒险队看不见 Koishi

猫猫冒险队只能引爆一个炸药桶,为了有更高的胜算,他们想知道引爆哪一个炸药桶才能让 Koishi 被炸到的概率最大。

输入格式

第一行输入三个正整数 ,用一个空格分隔, ,代表战斗场地有 行, 列。

接下来 行,每行三个正整数 ,用一个空格分隔 , 代表第 个炸药桶在第 行 , 第 列地板上 ,且爆炸半径为

输出格式

输出一行一个正整数 ,代表 Koishi 被炸到的最大概率为

样例

样例输入 1

3 3 3
1 1 1
2 1 1
3 1 1

样例输出 1

6

样例输入 2

3 3 1
2 2 1

样例输出 2

9