CF1523F Favorite Game

威廉在一天的工作结束后，喜欢玩他最喜欢的视频游戏。 这个游戏发生在一个二维世界中，从第 $0$ 回合开始。威廉可以选择游戏世界中的任意一个格子作为出生点。然后，每一回合，威廉可以选择留在当前位置，或者从当前位置 $(x, y)$ 移动到以下位置之一：$(x + 1, y)$、$(x - 1, y)$、$(x, y + 1)$、$(x, y - 1)$。 为了加快移动，游戏中有 $n$ 个快速传送塔。第 $i$ 个传送塔位于 $(xa_i, ya_i)$。要想从游戏世界的任意位置瞬间传送到该塔，必须先激活该塔。激活第 $i$ 个塔的方式是在玩家到达 $(xa_i, ya_i)$ 时激活，之后该塔在整个游戏过程中都保持激活状态。 威廉还知道，游戏中有 $m$ 个任务。第 $i$ 个任务可以在第 $t_i$ 回合时，玩家位于 $(xb_i, yb_i)$ 时瞬间完成。 威廉想知道，通过最优地在游戏世界中移动，他最多能完成多少个任务。

第一行包含两个整数 $n$ 和 $m$（$0 \le n \le 14, 1 \le m \le 100$），分别表示传送塔的数量和任务的数量。 接下来的 $n$ 行，每行包含两个整数 $xa_i, ya_i$（$1 \le xa_i, ya_i \le 10^6$），表示第 $i$ 个快速传送塔的坐标。 接下来的 $m$ 行，每行包含三个整数 $xb_i, yb_i, t_i$（$1 \le xb_i, yb_i \le 10^6, 1 \le t_i \le 10^9$），表示第 $i$ 个任务的坐标和可以完成该任务的回合数。 保证同一测试中的所有位置互不相同。

输出一个整数，表示威廉最多能完成的任务数。

在第一个样例测试中，威廉可能采取的行动序列如下： - 在 $(3, 2)$ 处出生。 - 第 $1$ 回合移动到 $(4, 2)$。 - 第 $2$ 回合移动到 $(5, 2)$，到达该格子时激活了第 $3$ 个传送塔。 - 第 $3$ 回合移动到 $(5, 1)$，在此处等待 $1$ 回合以完成第 $2$ 个任务。 - 第 $5$ 回合移动到 $(5, 2)$。 - 第 $6$ 回合移动到 $(5, 3)$。 - 第 $7$ 回合移动到 $(5, 4)$。 - 第 $8$ 回合移动到 $(5, 5)$。 - 第 $9$ 回合移动到 $(4, 5)$。 - 第 $10$ 回合移动到 $(3, 5)$，到达该位置时完成了第 $4$ 个任务。 - 第 $10$ 回合瞬间传送到已激活的快速传送塔 $(5, 2)$。 - 第 $11$ 回合移动到 $(6, 2)$，到达该位置时完成了第 $3$ 个任务。 - 威廉无法完成第 $1$ 个任务，因为 $(2, 3)$ 处的传送塔尚未激活。 由 ChatGPT 4.1 翻译