题目背景

原题为 P9125 [USACO23FEB] Cow-libi S

题目描述

有人偷偷吃了 Gooby 的零食！

Gooby 有 $M(1 \le M \le 10^5)$ 个柜子，柜子中放置着零食。每个柜子的位置都可以用笛卡尔坐标系（就是平面直角坐标系）中的坐标表示。

Gooby 有着丰富的断案经验，他判断出来了每个柜子中零食被偷吃的具体时间。他还发现，所有偷吃事件都是由一个单独的同学完成的。

为了表示自己是清白的，Gooby 的 $N(1 \le N \le 10^5)$ 个学生都提供了不在场证明，请你根据这些不在场证明，判断出有哪些同学是清白的。

具体来说，第 $i$ 个柜子的坐标是 $(x_i, y_i)$ ，它被偷吃的时间是 $t_i$ 。第 $j$ 个学生的不在场证明如下：在 $st_j$ 时间的时候，他在坐标 $(sx_j, sy_j)$。

如果一个同学无法在所有被偷吃地点和他的不在场证明位置之间来往，则可以确定他是清白的。同学的移动速度为每单位时间1单位的距离。如果一个同学要去吃某个柜子中的食物，他会按照两点之间线段最短的原则过去，也就是说距离是欧几里得距离。

输入格式

第一行包含两个用空格分隔的整数 $M$ 和 $N$。

接下来的 $M$ 行，每行包含三个用空格分隔的整数 $x, y, t$（$-10^9 \leq x, y \leq 10^9; 0 \leq t \leq 10^9$），描述某次偷吃事件的地点和时间。

输入保证至少有一个单独的学生可以在所有被偷吃地点之间往返。

接下来的 $N$ 行，每行包含 $x, y, t$（$-10^9 \leq x, y \leq 10^9; 0 \leq t \leq 10^9$），描述某个学生提供的“不在场证明”中提到的位置和时间。

输出格式

输出一个整数，表示能够证明清白的同学的数量。

输入输出样例 #1

输入 #1

2 4
0 0 100
50 0 200
0 50 50
1000 1000 0
50 0 200
10 0 170

输出 #1

2

样例 1 的解释

共有两次偷吃事件，第一次发生在 $(0,0)$，时间为 $100$；第二次发生在 $(50,0)$，时间为 $200$。

• 第一个学生可以在 $50$ 时间点从 $(0,50)$ 出发，花费 $50$ 的时间到 $(0,0)$ 偷吃，在原地等待 $50$ 时间后再花 $50$ 时间去 $(50,0)$ 去偷吃，刚好和所有偷吃事件和不在场证明的时间对的上。因此他无法证明自己的清白。
• 第二个学生的“不在场证明”能够证明她的清白。因为他从 $(1000,1000)$ 开始无法在 $100$ 时间点到达 $(0,0)$，也就无法继续偷吃。
• 第三个学生就在第二起偷吃事件的现场，显然这不能证明他的清白。
• 第四个学生是清白的，他可以在 $100$ 时间点去 $(0, 0)$ 偷吃，然后等 $60$ 时间点后花 $10$ 时间到达自己的不在场证明位置 $(10, 0)$，到达的时间点是 $170$， 但是他无论如何他都无法在 $200$ 时间点赶到 $(50,0)$ 。因此他是清白的。

评分标准

• 测试点 $1-3$：$1 \leq M, N \leq 10^3$。此外，对于偷吃地点和“不在场证明”，$-10^6 \leq x, y \leq 10^6$ 且 $0 \leq t \leq 10^6$。
• 测试点 $4-10$：无额外限制。