← 返回题目列表

Codeforces · 1523/F

F. 最喜欢的游戏

中文机器翻译题面 查看原题

William 完成一天的工作后,他喜欢玩他最喜欢的视频游戏。

游戏发生在 2D 世界中,从 $$$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$$$) 中的那一刻,此后塔在整个游戏中保持活动状态。

William 也知道游戏有 $$$m$$$ 任务。第 $$$i$$$ 个任务可以通过在 $$$t_i$$$ 回合到达位置 ($$$xb_i, yb_i$$$) 立即完成。

William 希望找出他通过最佳遍历游戏世界能够完成的最大任务数。

输入

第一行包含两个整数 $$$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$$$),它们是快速旅行塔的坐标。

接下来的 $$$m$$$ 行包含两个整数 $$$xb_i$$$、$$$yb_i$$$ 和 $$$t_i$$$ ($$$1 \le xb_i, yb_i \le 10^6$$$, $$$1 \le t_i \le 10^9$$$),它们是任务的坐标和它可以完成的回合。

保证测试中的所有位置都不同。

输出

打印一个数字——威廉能够完成的最大任务数。

示例

输入 #1

3 4
1 1
2 3
5 2
2 2 12
5 1 4
6 2 11
3 5 10

输出 #1

3

注意

在第一个示例测试中,William 的操作的可能顺序之一如下:

- 生成于 $$$(3, 2)$$$
- 回合 $$$1$$$ 移至 $$$(4, 2)$$$
- 在$$$2$$$回合中移动到$$$(5, 2)$$$。通过访问此牢房,威廉激活塔号 $$$3$$$。
- 在$$$3$$$回合中移动到$$$(5, 1)$$$,他在那里等待$$$1$$$回合来完成$$$2$$$nd任务
- 回合 $$$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$$$rd 任务
- 威廉将无法完成任务号 $$$1$$$,因为 $$$(2, 3)$$$ 处的塔未激活