CF702F T-Shirts

一批春季前上新的 T 恤将在商店内出售。一共有 $n$ 种不同类型的 T 恤。第 $i$ 种 T 恤有两个整数参数 —— $c_{i}$ 和 $q_{i}$，其中 $c_{i}$ 表示第 $i$ 种 T 恤的价格，$q_{i}$ 表示第 $i$ 种 T 恤的质量。商店中每种类型的 T 恤都可以无限购买，但总体上质量与价格无关。 预计在下个月内会有 $k$ 位顾客来到商店，第 $j$ 位顾客打算花费最多 $b_{j}$ 元购买 T 恤。 所有顾客的购买策略相同。首先，顾客会优先购买尽可能多的质量最高的 T 恤，然后在剩余的 T 恤中继续尽量多地购买质量次高的 T 恤，以此类推。对于同等质量的多种 T 恤，顾客会选择价格更便宜的那款。每位顾客对同一种 T 恤只会购买一件，且顾客们互不影响，彼此购买独立。 请你计算，对于每位顾客，按照上述策略他会买多少件 T 恤。

第一行包含一个正整数 $n$（$1\leq n\leq 2\times 10^{5}$），表示 T 恤的类型数。 接下来的 $n$ 行，每行包含两个整数 $c_{i}$ 和 $q_{i}$（$1\leq c_{i}, q_{i}\leq 10^{9}$），分别表示第 $i$ 种 T 恤的价格和质量。 接下来一行包含一个正整数 $k$（$1\leq k\leq 2\times 10^{5}$），表示顾客人数。 接下来一行包含 $k$ 个正整数 $b_{1}, b_{2}, \ldots, b_{k}$（$1\leq b_{j}\leq 10^{9}$），其中 $b_{j}$ 表示第 $j$ 位顾客准备花在 T 恤上的钱数。

输出一行，共 $k$ 个整数，第 $i$ 个整数表示第 $i$ 位顾客最终购买的 T 恤数量。

在第一个样例中，第一位顾客会先买第二种 T 恤，再买第一种 T 恤。他一共花费了 10 元，但买不起第三种 T 恤（需要 4 元，剩下只剩 3 元）。第二位顾客可以买下三种 T 恤（先买第二种，再买第一种，最后买第三种），正好花光所有的钱。 由 ChatGPT 5 翻译