← 返回题目列表

Codeforces · 702/F

F. T 恤

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

开春前,店内将大量发售T恤。共有 n 种 T 恤发售。第 i 种 T 恤有两个整数参数——ci 和 qi,其中 ci 是第 i 种 T 恤的价格,qi 是第 i 种 T 恤的质量。应该假设商店里出售的每种类型的 T 恤数量不受限制,但一般来说质量与价格无关。

正如预测,下个月内将有 k 位顾客来到商店,第 j 位顾客将准备花费最多 bj 购买 T 恤。

所有客户都有相同的策略。首先,顾客希望购买尽可能多的最高质量的T恤,然后从剩余的T恤中购买尽可能多的最高质量的T恤,依此类推。同时,在多件相同质量的T恤中,顾客会购买更便宜的一件。顾客不喜欢相同的T恤,因此每个顾客不会购买超过一件同一种类型的T恤。

确定每个客户如果使用所描述的策略,将购买的 T 恤数量。所有客户的行为都是独立的,一个客户的购买不会影响另一个客户的购买。

输入

第一行包含正整数 n (1 ≤ n ≤ 2·105) — T 恤类型的数量。

以下 n 行每行包含两个整数 ci 和 qi (1 ≤ ci, qi ≤ 109) — 第 i 种 T 恤的价格和质量。

下一行包含正整数 k (1 ≤ k ≤ 2·105) — 客户数量。

下一行包含 k 个正整数 b1, b2, ..., bk (1 ≤ bj ≤ 109),其中第 j 个数字等于第 j 个顾客准备购买 T 恤的总和。

输出

输入数据的第一行应包含 k 个整数的序列,其中第 i 个数字应等于第 i 个客户将购买的 T 恤的数量。

示例

输入 #1

3
7 5
3 5
4 3
2
13 14

输出 #1

2 3

输入 #2

2
100 500
50 499
4
50 200 150 100

输出 #2

1 2 2 1

注意

在第一个示例中,第一个客户将购买第二种类型的 T 恤,然后购买第一种类型的 T 恤。他将花费 10 美元,并且无法购买第三种类型的 T 恤,因为它花费 4 美元,而客户只欠 3 美元。第二个客户将购买所有三件 T 恤(首先是第二种类型的 T 恤,然后是第一种类型的 T 恤,然后是第三种类型的 T 恤)。他会花掉所有的钱。