AT_tkppc3_g.パソコンの買い替え

在 Thistle 君所居住的世界中，总共有 $N$ 家公司，每家公司都生产一种型号的电脑。这些电脑的性能经过岁月变迁以指数方式提升，具体来说，第 $i$ 家公司（$1 \leq i \leq N$）生产的电脑，在从现在起恰好 $x$ 年后的性能为 $a_i \cdot b_i^{x - r_i}$。

Thistle 君计划在未来的 $K$ 次换购中，每次都购买性能最优的电脑。如果碰上多台电脑性能相同，他可以任意选购其中一台。他希望能够借此机会尽可能多地尝试不同公司的电脑，因此希望在这 $K$ 次换购中能购买到的不同公司出品的电脑种类数最大化。请帮他计算一下，最多能买到多少家公司的电脑。

输入以如下的形式给出：

$N$ $a_1$ $b_1$ $r_1$ $a_2$ $b_2$ $r_2$ ... $a_N$ $b_N$ $r_N$ $K$ $y_1$ $y_2$ ... $y_K$

各数据之间用空格分隔，其中：

• $N$ 表示公司的数量
• $a_i$、$b_i$、$r_i$ 是第 $i$ 家公司的参数
• $K$ 表示要进行的换购次数
• $y_i$ 是第 $i$ 次换购的时间点（年）

输出一个整数，表示在 $K$ 次换购中，Thistle 君最多能购买到的不同公司生产的电脑种类数。

• $N$ 和 $K$ 均为 $1$ 到 $200\,000$ 之间的整数。
• $a_i$ 为 $1$ 到 $200\,000$ 之间的整数。
• $b_i$ 为 $2$ 到 $200\,000$ 之间的整数。
• $r_i$ 的范围是 $0$ 到 $200\,000$。
• 每次换购的时间点 $y_i$ 为 $0$ 到 $200\,000$，而且满足 $y_1 < y_2 < \cdots < y_K$。
• 在每次电脑换购时，性能最好的电脑和第二好的电脑的性能差距足够大，至少相差 $1 + 10^{-11}$ 倍。如果有多台电脑性能并列第一，它们与其他电脑的性能差距也超过 $1 + 10^{-11}$ 倍。（16:06 更新）

子任务

子任务 1 [200 点]

• $N, K \leq 1\,000$

子任务 2 [500 点]

• 没有额外限制条件。

本翻译由 AI 自动生成