← 返回题目列表

Codeforces · 198/E

E. 扣人心弦的故事

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

有一天,游侠 Qwerty 目睹了两艘运输船相撞。结果,他们的货舱里的所有东西都散落在整个空间里。现在 Qwerty 希望捡起尽可能多的丢失物品​​以便稍后出售。

问题是,两艘船都有很多新的重力夹具,被运输来出售。夹具是一种可以安装在宇宙飞船上的装置,可以将太空中的物品吸引到自身(“夹具”)并将它们运输到飞船的货舱。

总的来说,坠毁的船只失去了 n 个重力夹具:第 i 个夹具位于坐标为 (xi, yi) 的点。每个夹具都有两个特征——pi(功率)和ri(作用半径),可以抓取任何质量不超过pi、距离不超过ri的物体。夹具本身也是一个物品,它有它的质量 mi。

Qwerty 的船位于 (x, y) 点,安装了一个旧的磁力夹具,其特征为 p 和 r。船上的货舱内没有其他夹具。

找出 Qwerty 可以抓住的最大数量的夹具。当他拾取物品时,他可以在船的货舱中任意安装任何抓手,包括他刚刚拾取的抓手。在任何时候,船上只能安装一个主动夹具。当护林员拾取物品时,我们认为所有物品和 Qwerty 的船都是静止的,除非夹具移动物品 - 然后物品移动到货舱,而船仍然保持不动。我们可以假设船上的货舱有足够的空间容纳所有夹具。 Qwerty 可以使用他找到的任何夹具或初始夹具任意次数。

输入

第一行包含五个整数 x、y、p、r 和 n (- 109 ≤ x, y ≤ 109, 1 ≤ p, r ≤ 109, 1 ≤ n ≤ 250000) — 船舶的初始位置、初始夹具的特征以及碰撞期间进入空间的夹具的数量。

接下来 n 行包含夹具的描述:第 i 行包含五个整数 xi, yi, mi, pi, ri (- 109 ≤ xi, yi ≤ 109, 1 ≤ mi, pi, ri ≤ 109) — 第 i 个夹具的坐标和特征。

确保所有夹具都位于不同的点。没有夹具与 Qwerty 的船位于同一点。

输出

打印一个数字——Qwerty 可以吸引到他的船上的夹具的最大数量。您不需要计算最初的旧磁铁夹具。

示例

输入 #1

0 0 5 10 5
5 4 7 11 5
-7 1 4 7 8
0 2 13 5 6
2 -3 9 3 4
13 5 1 9 9

输出 #1

3

注意

在第一个示例中,您应该获取第二个夹具,然后使用第二个夹具获取第一个夹具,然后使用第一个夹具获取第四个夹具。你既拿不到第三个夹具,因为它太重,也拿不到第五个夹具,因为它太远。