C-总辖之愿_金山杯2025年武汉理工大学程序设计竞赛

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
Special Judge, 64bit IO Format: %lld

题目描述

璃寒和曜灵是一对好朋友。

某一天，璃寒告诉曜灵，一种名为"挖矿"的方法非常赚钱，于是曜灵就想要前往另一个星球去挖矿，虽然她的理解完全错误，但是她真的找到了一个可以视为具有 $n\times m$ 的网格的矩形的富含矿物的星球，她在这颗星球上建造了中心点互不重合的 $k$ 座矿场，一座编号为 $i$ 的矿场可以被它的中心点坐标 $(x_i,y_i)$ 和延伸距离 $dis_i$ 确定，具体地，一个网格 $(x_{now},y_{now})$ 在这个矿场，当且仅当 $x_{now}$ 与 $y_{now}$ 不超过该星球的范围且同时满足 $|x_i-x_{now}|\leq dis_i$ 和 $|y_i-y_{now}|\leq dis_i$ 。

建造完这些矿场后，曜灵还需要运输线确保这些矿物能够送回地球进行售卖，真正达到赚钱的目的，于是她还需要确定一个中心点在 $(x_{ans},y_{ans})$ 、支撑距离 $dis_{ans}$ 且所有占据的格子不在矿场中的发射台以方便火箭来往，一个网格 $(x_{lanuch},y_{lanuch})$ 被发射台占据，当且仅当 $x_{lanuch}$ 与 $y_{lanuch}$ 不超过该星球的范围且 $|x_{ans}-x_{lanuch}|+|y_{ans}-y_{lanuch}|\leq dis_{ans}$ 。

由于曜灵非常聪明，所以你只需要输出符合条件的发射台的最大支撑距离 $dis_{ans}$ 即可，曜灵会自己找位置建的，如果曜灵没那么聪明，让你找不到任何一个可以建造的位置，请输出 '-1'(不包含单引号)。

需要注意的是，矿场和发射台占据的区域可以超过星球，但是中心点一定需要在星球中。

输入描述:

第一行，三个整数 ,,，表示矩形的大小和矿场个数。

第  行到第  行每行三个整数，其中第  行的整数为 ,,，表示第  座矿场的中心点和延伸距离。

输出描述:

共一行，一个整数 ，表示符合条件的发射台的最大支撑距离。

示例1

输入

复制

5 6 2
2 2 2
5 6 1

输出

复制

示例2

输入

复制

5 5 1
3 3 2

输出

复制

-1

备注:

样例 1 解释：



带下划线的数字为矿场的中心点，矿场格已被标出，此时中心点为  或 ，支撑距离为 1 的发射台是支撑距离最大的选择地点。

样例 2 解释：

由于矿场的范围占据了整颗星球，所以没有任何一个位置建造发射台，输出 '-1'。