CF1523F.Favorite Game

After William is done with work for the day, he enjoys playing his favorite video game.

The game happens in a 2D world, starting at turn $0$. William can pick any cell in the game world and spawn in it. Then, each turn, William may remain at his current location or move from the current location (x, y) to one of the following locations: (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1).

To accelerate movement the game has $n$ fast travel towers. $i$-th tower is located at location ($xa_i, ya_i$). To be able to instantly travel to the tower from any location in the game world it must first be activated. Activation of tower $i$ happens at the moment when the player is in cell ($xa_i, ya_i$) after this the tower remains active throughout the entire game.

William also knows that the game has $m$ quests. $i$-th quest can be completed instantly by being at location ($xb_i, yb_i$) on turn $t_i$.

William wants to find out the maximal number of quests he will be able to complete by optimally traversing the game world.

威廉每天工作结束后，喜欢玩他最钟爱的电子游戏。

该游戏发生在一个二维世界中，起始时刻为第 $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)$ 处时立即完成。

威廉希望确定：通过在游戏世界中进行最优路径规划，他最多能完成多少个任务。

The first line contains two integers $n$ and $m$ ($0 \le n \le 14, 1 \le m \le 100$), which are the number of towers and the number of quests, respectively.

Each of the next $n$ lines contains two integers $xa_i, ya_i$ ($1 \le xa_i, ya_i \le 10^6$), which are the coordinates of fast travel towers.

Each of the next $m$ lines contains two integers $xb_i$, $yb_i$ and $t_i$ ($1 \le xb_i, yb_i \le 10^6$, $1 \le t_i \le 10^9$), which are the coordinates of quests and the turn at which it may be completed.

It is guaranteed that all locations in a test are different.

第一行包含两个整数 $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$ 个任务的坐标以及该任务可被完成的回合数。

保证测试用例中所有位置互不相同。

Print a single number — the maximal number of quests William will be able to complete.

输出一个整数——威廉能够完成的任务的最大数量。

In the first sample test one of the possible sequences of William's actions is as follows:

• Spawn at $(3, 2)$
• On turn $1$ move to $(4, 2)$
• On turn $2$ move to $(5, 2)$. By visiting this cell William activates tower number $3$.
• On turn $3$ move to $(5, 1)$, where he waits for $1$ turn to complete the $2$nd quest
• On turn $5$ move to $(5, 2)$
• On turn $6$ move to $(5, 3)$
• On turn $7$ move to $(5, 4)$
• On turn $8$ move to $(5, 5)$
• On turn $9$ move to $(4, 5)$
• On turn $10$ move to $(3, 5)$. By moving to this location William will complete the $4$th quest
• On turn $10$ instantly move to an already activated fast travel tower at $(5, 2)$
• On turn $11$ move to $(6, 2)$. By moving to this location William will complete the $3$rd quest
• William will not be able to complete the quest number $1$, because the tower at $(2, 3)$ was not activated

在第一个样例测试中，威廉可能采取的操作序列之一如下：

• 在 $(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)$ 的塔未被激活