题目描述

在一个狂热的粉丝团队里，有 $N$ 个人，每个人的情绪指数可以用一个整数衡量，其中第 $i$ 个人的情绪指数为 $H_i$。

经纪人希望将 $M$ 件商品卖给这些粉丝。其中第 $j$ 件商品的价值为 $V_j$。一般来说，这个商品就只能卖出 $V_j$ 元，不过粉丝可以接受溢价。具体来说，如果一件商品的定价为 $P$，溢价可以表示为 $P-V_j$，只要粉丝 $i$ 的情绪指数 $H_i\geq P-V_j$，那么他就会掏出 $P$ 元购买这件商品。

请为每一件商品确定一个价格，使得在这个价格下，面向粉丝的销售金额达到最高，输出每件商品的最高销售金额。一件商品的销售金额是它的售价乘以它的销售量。

输入格式

• 第一行：两个整数 $N$ 与 $M$
• 第二行：$N$ 个整数 $H_1,H_2,\dots,H_N$
• 接下来 $M$ 行：每行一个整数表示 $V_1,\dots,V_M$

输出格式

• 共 $M$ 行：每行一个数表示一件商品的最高销售金额。

4 3
0 2 5 10
1
3
5

12
16
21

数据范围

• $30\%$ 的数据，$1\leq N, M\leq 1,000$
• $60\%$ 的数据，$1\leq N, M\leq 20,000$
• $100\%$ 的数据，$1\leq N, M\leq 300,000$
• $0\leq V_i\leq 10^9$
• $0\leq H_j\leq 10^9$

来源

改编自 ABC289G Shopping in AtCoder store